Proving that greedy algorithm on TSP does not produce optimal solution

1.3k Views Asked by At

I know that solving a TSP requires considering all possible cycles in the graph, and that a nearest neighbor greedy algorithm does not always produce the shortest path. I found this answer that gives a counterexample for such a greedy algorithm, but it only consider starting from a specific vertex (A). My question is, if we apply this greedy algorithm n times starting at each of the n vertex, why wouldn't it yields an optimal short path? I didn't manged to come up with any counterexample yet.

1

There are 1 best solutions below

2
On BEST ANSWER

Here is a counterexample where the optimal solution is of weight $13$ but it takes more than $100$ if we use the greedy algorithm starting from any vertex:

enter image description here