Christofides’ algorithm is an approximation algorithm for solving the Traveling Salesman Problem (TSP) on weighted graphs that satisfy the triangle inequality. It guarantees a tour that is at most 1.5 times the cost of the optimal solution. The algorithm works by building a Minimum Spanning Tree (MST), finding a minimum-weight perfect matching on the odd-degree vertices, and combining them into an Eulerian multigraph, which is then converted into a Hamiltonian cycle using shortcutting.
Sourcecode: