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.
2026-03-27 01:13:29.1774574009
Proving that greedy algorithm on TSP does not produce optimal solution
1.3k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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: