christofides

christofides(G, weight='weight', tree=None)[source]

Approximate a solution of the traveling salesman problem

Compute a 3/2-approximation of the traveling salesman problem in a complete undirected graph using Christofides [1] algorithm.

Parameters
GGraph

G should be a complete weighted undirected graph. The distance between all pairs of nodes should be included.

weightstring, optional (default=”weight”)

Edge data key corresponding to the edge weight. If any edge does not have this attribute the weight is set to 1.

treeNetworkX graph or None (default: None)

A minimum spanning tree of G. Or, if None, the minimum spanning tree is computed using networkx.minimum_spanning_tree()

Returns
list

List of nodes in G along a cycle with a 3/2-approximation of the minimal Hamiltonian cycle.

References

1

Christofides, Nicos. “Worst-case analysis of a new heuristic for the travelling salesman problem.” No. RR-388. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976.