Christofides Algorithm, in depth: the five steps, the full 3/2 proof, a runnable implementation, the tight instance and 2-opt clean-up

The five steps

The input is a complete graph whose edge weights form a metric. Weights are non-negative and symmetric, and d(a, c) ≤ d(a, b) + d(b, c) for every triple. Distances between points in the plane qualify. Road travel times usually do too, after you take shortest paths. The algorithm has five steps:

1. Minimum spanning tree. Compute an MST T of the graph.
2. Odd vertices. Let O be the set of vertices with odd degree in T.
3. Matching. Compute a minimum-weight perfect matching M on the complete graph induced by O.
4. Euler circuit. The multigraph T + M has every degree even, so it has an Eulerian circuit, a closed walk that uses every edge exactly once.
5. Shortcut. Walk the circuit and skip any vertex already visited. What remains is a Hamiltonian cycle: the tour.

Each step is a classic algorithm with its own page: Prim's algorithm for step 1, Edmonds' blossom algorithm for step 3, and Hierholzer's algorithm for step 4. Christofides' contribution is the way they combine, and the proof that the result is never more than 50 percent too long.

Why the tour is at most 1.5 times optimal

Let OPT be the length of an optimal tour. The proof bounds each piece of T + M against OPT.

The tree costs at most OPT. Delete any edge from the optimal tour and you get a Hamiltonian path, which is a spanning tree. The MST is no heavier than any spanning tree, so w(T) ≤ OPT. Strictly it is less, by the length of the deleted edge.

O has an even number of vertices. The sum of degrees in any graph is twice the number of edges, so it is even. The even-degree vertices contribute an even amount, so the odd-degree vertices must also sum to an even number, which needs an even count of them. A perfect matching on O therefore exists.

The matching costs at most OPT / 2. Take the optimal tour and shortcut it to visit only the vertices of O, in tour order. By the triangle inequality the shortcut cycle is no longer than OPT. It is a cycle on an even number of vertices, so its edges alternate into two perfect matchings of O. Their total is at most OPT, so the cheaper one costs at most OPT / 2. The minimum matching M is no worse: w(M) ≤ OPT / 2.

Every degree in T + M is even. Each vertex in O gains exactly one matching edge, turning odd into even. The other vertices are untouched. A connected multigraph with all degrees even has an Euler circuit of length w(T) + w(M) ≤ 1.5 · OPT.

Shortcutting never lengthens the walk. Replacing a path a → ... → c by the direct edge a → c cannot increase length under the triangle inequality. The final tour is therefore at most 1.5 · OPT. Every inequality uses the triangle inequality or the minimality of T and M, so drop either and the guarantee is gone.

An implementation in Python

With networkx providing the three sub-algorithms, the implementation stays short. Note the MultiGraph. It is the most important line in the function, and the failure-modes section explains why.

import itertools, math
import networkx as nx

def christofides(points):
    n = len(points)
    G = nx.Graph()
    for i, j in itertools.combinations(range(n), 2):
        G.add_edge(i, j, weight=math.dist(points[i], points[j]))

    T = nx.minimum_spanning_tree(G, weight="weight")              # step 1
    odd = [v for v in T if T.degree(v) % 2 == 1]                  # step 2
    M = nx.min_weight_matching(G.subgraph(odd), weight="weight")  # step 3

    H = nx.MultiGraph(T)          # keep parallel edges: T and M may share one
    H.add_edges_from(M)
    tour, seen = [], set()
    for u, _ in nx.eulerian_circuit(H, source=0):                 # step 4
        if u not in seen:                                         # step 5
            seen.add(u)
            tour.append(u)
    tour.append(tour[0])
    length = sum(G[a][b]["weight"] for a, b in zip(tour, tour[1:]))
    return tour, length

networkx also ships the whole algorithm as nx.approximation.christofides(G, weight='weight', tree=None), which accepts a precomputed tree. On the example below it returned the same tour as this function. Writing it out once is still worth it, because when a tour looks wrong you need to inspect T, O and M separately.

Worked example: eight cities

Take eight cities at (0,0), (4,0), (8,0), (8,3), (4,4), (0,3), (2,7) and (6,7), numbered 0 to 7, with Euclidean distances. Running the code above with networkx 3.7 gives:

The tour is 1.186 times the optimum, comfortably inside the 1.5 bound of 45.2. The bound is a ceiling, not a forecast. Over 200 random ten-city instances in the unit square, the worst ratio measured was 1.226. Look at the matching: vertices 1 and 4 are already joined by a tree edge, and the cheapest way to fix their parity is a second copy of that same edge. The circuit walks 1 → 4 twice, and shortcutting removes the repeats of 1 and 4. The exact optimum came from Held-Karp dynamic programming, which is feasible here because n = 8.

Where the time goes

The running time is dominated by step 3. On a complete graph with n vertices:

Just building the complete graph costs O(n²) memory. Ten thousand cities means 50 million edges, which pure-Python graph libraries cannot handle. Past a few thousand points, real systems change the pipeline. They build a sparse candidate graph, such as the k nearest neighbours of each city or a Delaunay triangulation, and compute the MST on that. A Euclidean MST is always a subgraph of the Delaunay triangulation, so nothing is lost there. They may also replace exact matching with a greedy or approximate matching. That last change gives up the 3/2 proof, so state it if you make it.

The tight instance and tie-breaking

The 1.5 bound is tight: there are inputs where Christofides' output approaches 1.5 times the optimum. The classic family is a strip of equilateral triangles with unit sides, with points alternating between two parallel lines. If the MST is the zig-zag path through every point, it has only two odd vertices, its two ends. They sit about n/2 apart, so the matching adds one long edge and the tour approaches 1.5n, while the optimal tour, out along one line and back along the other, has length close to n.

Many spanning trees on this input have the same minimum weight, so the bad case depends on which tie the MST routine picks. When we ran the code above on strips of 11 to 81 points, networkx broke the ties differently and returned near-optimal tours. That is worth knowing. Tie-breaking in step 1 can change the output by tens of percent, so running the algorithm with a few randomised tie-breaks and keeping the best tour is a cheap improvement.

2-opt: the pass everyone adds

In practice almost nobody ships a raw Christofides tour. The tour has a guarantee, but it often contains crossing edges, and in the plane a tour with a crossing is never optimal. 2-opt local search removes crossings. It repeatedly picks two edges (a, b) and (c, d), and if a–c plus b–d is shorter it reverses the segment between them:

def two_opt(tour, d):
    """tour: closed list [v0, ..., v0]; d(u, v): distance. Returns an improved tour."""
    best = tour[:]
    improved = True
    while improved:
        improved = False
        for i in range(1, len(best) - 2):
            for j in range(i + 1, len(best) - 1):
                a, b, c, e = best[i - 1], best[i], best[j], best[j + 1]
                if d(a, c) + d(b, e) < d(a, b) + d(c, e) - 1e-12:
                    best[i:j + 1] = reversed(best[i:j + 1])
                    improved = True
    return best

On the eight-city example, 2-opt turns the 35.769 tour into 0 1 2 3 7 4 6 5 0 at 30.155, which is the optimum. The long crossing edge 2–6 disappears. 2-opt never makes a tour longer, so the 3/2 guarantee survives. Christofides supplies a good, provable starting point, and local search supplies most of the practical quality. For larger instances, Or-opt and Lin-Kernighan moves go further, and metaheuristics such as simulated annealing can escape 2-opt's local optima.

Failure modes

• Using a simple Graph for T + M. When a matching edge duplicates a tree edge, as 1–4 does above, a simple graph silently merges them. Two vertices stay odd and the Euler circuit fails, or a library raises. Always use a multigraph.
• Greedy matching. Pairing odd vertices greedily is fast, but the OPT / 2 argument needs a minimum perfect matching. Greedy matching has no constant-factor guarantee against the minimum, so the 3/2 proof no longer holds.
• Non-metric inputs. Asymmetric costs, such as one-way streets, or costs that violate the triangle inequality break the shortcut step. Repair them by replacing each cost with the shortest-path distance, then map each tour edge back to its path.
• Matching on the wrong graph. The matching must use the complete graph on O with true distances, not only the edges of the tree or of a sparse candidate graph.
• Floating-point ties. Near-equal distances make the MST and the matching unstable between runs and platforms. Round or scale to integers if you need reproducible tours.
• Quoting 1.5 as the expected ratio. It is a worst-case ceiling. Report measured ratios against a lower bound, for example the MST length, which is at most OPT.

Trade-offs

Choose Christofides when you need a written guarantee, for example in a contract, a proof or a benchmark baseline, or when you want a strong, deterministic seed for local search. The cubic matching step is the price, and beyond a few thousand cities it dominates. If you only need good tours fast, nearest-neighbour or greedy-edge construction plus 2-opt or Or-opt is simpler and usually just as good in practice. For provably optimal answers on small inputs, use Held-Karp up to about 20 cities, or an integer-programming solver beyond that. The MST-doubling 2-approximation is easier still, and worth keeping as a sanity check: Christofides should never lose to it by much.

What to do next

1. Check that your distances are a metric. If not, replace them with shortest-path distances.
2. Implement the five steps with a multigraph, and log the MST, odd set and matching weights.
3. Validate on small instances against Held-Karp, and assert that every tour is at most 1.5 times the optimum.
4. Add 2-opt after the shortcut step and measure the improvement on your own data.
5. Run several randomised MST tie-breaks and keep the best tour.
6. Above a few thousand cities, move to a sparse candidate graph and document any approximate matching that voids the guarantee.
7. Report measured ratios against the MST lower bound, not the theoretical 1.5.