TSP in Python: Christofides, 2-opt, 3-opt

algorithms
python
A short, practical walkthrough of three classic TSP algorithms with working Python code.
Author

Matej Gazda

Published

February 8, 2019

Modified

May 14, 2026

The travelling salesman problem (TSP) is one of those textbook problems that sounds simple and turns out not to be: given a list of cities and the distances between them, find the shortest tour that visits every city exactly once and returns to the start.

It’s NP-hard in the general case, so unless you have ten cities or a quantum computer, you’ll want an approximation. Below are the three algorithms I implemented in pytsp, with just enough math to understand what’s going on.

Christofides (the 1.5-approximation)

Christofides only works on metric TSP instances: distances must be symmetric and obey the triangle inequality. In return it gives you a tour guaranteed to be at most 1.5× the optimal length. It is still the best constant-factor approximation known for metric TSP that doesn’t depend on exotic results.

The recipe:

  1. Build a minimum spanning tree T of the graph.
  2. Find the set O of vertices with odd degree in T.
  3. Compute a minimum-weight perfect matching M on O.
  4. Combine T ∪ M into a multigraph. Every vertex now has even degree.
  5. Find an Eulerian circuit.
  6. Shortcut repeated vertices (use the triangle inequality to make a Hamiltonian cycle out of it).

The trickiest step is the matching. networkx ships max_weight_matching, which finds a maximum-weight matching, so to get the minimum one I flip the sign of the weights. That only works because the algorithm doesn’t drop edges with negative weights when you ask for maximum cardinality. Subtracting weights from a large constant is the cleaner trick if you want positive numbers.

For Euler circuits and MSTs, just use networkx. No need to reinvent.

# pseudo-summary; full code in pytsp/christofides.py
mst   = prim(graph)
odd   = [v for v in mst if mst.degree(v) % 2]
match = min_weight_perfect_matching(graph, odd)
H     = nx.MultiGraph(mst); H.add_edges_from(match)
tour  = list(nx.eulerian_circuit(H))
tour  = shortcut(tour)  # remove repeats

2-opt (the workhorse)

2-opt is the simplest local-search heuristic for TSP. Start with any tour. Repeatedly: pick two non-adjacent edges, delete them, and reconnect the two resulting paths the other way. Keep the change if the new tour is shorter.

... → A — B ... C — D → ...        (original)
... → A — C ... B — D → ...        (after a 2-opt swap)

The middle segment between B and C gets reversed. The move costs O(1) to evaluate (d(A,C) + d(B,D) − d(A,B) − d(C,D)), and a full pass over all candidate pairs is O(n²). The algorithm terminates at a local minimum where no swap improves the tour.

In practice 2-opt converges fast and gets within a few percent of the optimum on Euclidean instances. It’s the default starting point for any TSP code.

3-opt (the bigger hammer)

3-opt removes three edges instead of two, breaking the tour into three segments A, B, C. There are 8 ways to reconnect them (including the original), of which 4 are real 3-opt moves and 3 are equivalent to 2-opt moves. So you really only have 4 new moves to consider.

The cost-change function compares each reconnection’s total edge weight against the original. Whichever case wins, you splice the segments back in the right order (with some reversed). The cost per move is still O(1) to evaluate; the bottleneck is the O(n³) iteration over edge triples.

A small implementation sketch:

for i, j, k in triples(route):
    best_case, best_gain = argmin_cases(graph, route, i, j, k)
    if best_gain < 0:
        route = apply_case(route, i, j, k, best_case)

3-opt finds better local optima than 2-opt, at the cost of n times more work per iteration. Use it when 2-opt is stuck and you can afford the runtime.

What to use when

  • Small symmetric metric instances, want a guarantee: Christofides.
  • Any instance, fast and good enough: 2-opt from a greedy or random start.
  • Squeezing the last few percent: 3-opt, or move to LKH / Concorde for serious work.

Full implementations are on GitHub: BraveDistribution/pytsp. PRs welcome. The code is years old at this point and could use a Kruskal implementation, better tests, and a benchmark script.

References

  • Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. CMU Tech Report (1976).
  • Lin, S.; Kernighan, B. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research 21(2), 1973.
  • Helsgaun, K. An effective implementation of the Lin–Kernighan traveling salesman heuristic. EJOR 126(1), 2000.
  • TSP basics blog: https://tsp-basics.blogspot.com/
Back to top