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.