Graph algorithms / interactive lesson
Approximate metric TSP with Doubletree and Christofides. Compare MST lower bounds, Eulerian multigraphs, shortcutting, and the 2 versus 3/2 guarantees.
Approximation timeline
Doubletree starts from an MST
About the algorithm
Metric Traveling Salesman asks for the cheapest tour that visits every city exactly once and returns home, assuming distances are symmetric and obey the triangle inequality. Doubletree and Christofides are classic approximation algorithms: they trade exact optimality for provable guarantees.
Doubletree first builds a minimum spanning tree, duplicates every tree edge to make all degrees even, follows an Euler walk, and shortcuts repeated cities. The shortcut step is safe only because the graph is metric. Its tour costs at most twice the optimum.
Christofides also starts with an MST, but it adds only a minimum-weight perfect matching on odd-degree tree vertices. The resulting multigraph is Eulerian, so an Euler tour followed by shortcutting gives a Hamiltonian cycle. The guarantee improves to 3/2 of the optimum.
The triangle inequality says that going directly from A to C is never more expensive than detouring through B. That is exactly what lets both algorithms remove repeated vertices from an Euler walk without increasing the tour length.
Code companion
Connect each visual decision to an implementation pattern.
T = minimum_spanning_tree(G)
H = duplicate_every_edge(T)
W = euler_tour(H)
tour = shortcut_repeated_vertices(W)
return tour