This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route - for small cases it would seem any (undirected) complete weighted graph with this property forces the FN algorithm to produce an equally bad route.

Naturally this raises the question whether FN can ever produce a shorter path than NN - I am mostly interested in the symmetric TSP here. Any input would be greatly appreciated.

Posted on MSE over a year ago, with no answers.

4more comments