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
Gshould 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
Galong 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.