Skip to main content
`Ctrl`+`K`

# christofides

christofides(G, weight='weight', tree=None)

  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:
    G Graph

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

    weight string, 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.

    tree NetworkX 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.