Skip to main content
`Ctrl`+`K`

# traveling_salesman_problem

traveling_salesman_problem(G, weight='weight', nodes=None, cycle=True, method=None, **kwargs)

  Find the shortest path in `G` connecting specified nodes

  This function allows approximate solution to the traveling salesman problem on networks that are not complete graphs and/or where the salesman does not need to visit all nodes.

  This function proceeds in two steps. First, it creates a complete graph using the all-pairs shortest_paths between nodes in `nodes`. Edge weights in the new graph are the lengths of the paths between each pair of nodes in the original graph. Second, an algorithm (default: `christofides` for undirected and `asadpour_atsp` for directed) is used to approximate the minimal Hamiltonian cycle on this new graph. The available algorithms are:

  > - christofides

  > - greedy_tsp

  > - simulated_annealing_tsp

  > - threshold_accepting_tsp

  > - asadpour_atsp

  Once the Hamiltonian Cycle is found, this function post-processes to accommodate the structure of the original graph. If `cycle` is `False`, the biggest weight edge is removed to make a Hamiltonian path. Then each edge on the new complete graph used for that analysis is replaced by the shortest_path between those nodes on the original graph. If the input graph `G` includes edges with weights that do not adhere to the triangle inequality, such as when `G` is not a complete graph (i.e length of non-existent edges is infinity), then the returned path may contain some repeating nodes (other than the starting node).

  Parameters:
    G NetworkX graph

      A possibly weighted graph

    nodes collection of nodes (default=G.nodes)

      collection (list, set, etc.) of nodes to visit

    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.

    cycle bool (default: True)

      Indicates whether a cycle should be returned, or a path. Note: the cycle is the approximate minimal cycle. The path simply removes the biggest edge in that cycle.

    method function (default: None)

      A function that returns a cycle on all nodes and approximates the solution to the traveling salesman problem on a complete graph. The returned cycle is then used to find a corresponding solution on `G`. `method` should be callable; take inputs `G`, and `weight`; and return a list of nodes along the cycle.

      Provided options include `christofides()`, `greedy_tsp()`, `simulated_annealing_tsp()` and `threshold_accepting_tsp()`.

      If `method is None`: use `christofides()` for undirected `G` and `asadpour_atsp()` for directed `G`.

    **kwargs dict

      Other keyword arguments to be passed to the `method` function passed in.

  Returns:
    list

      List of nodes in `G` along a path with an approximation of the minimal path through `nodes`.

  Raises:
    NetworkXError

      If `G` is a directed graph it has to be strongly connected or the complete version cannot be generated.

  Examples

      >>> tsp = nx.approximation.traveling_salesman_problem
      >>> G = nx.cycle_graph(9)
      >>> G[4][5]["weight"] = 5  # all other weights are 1
      >>> tsp(G, nodes=[3, 6])
      [3, 2, 1, 0, 8, 7, 6, 7, 8, 0, 1, 2, 3]
      >>> path = tsp(G, cycle=False)
      >>> path in ([4, 3, 2, 1, 0, 8, 7, 6, 5], [5, 6, 7, 8, 0, 1, 2, 3, 4])
      True

  While no longer required, you can still build (curry) your own function to provide parameter values to the methods.

      >>> SA_tsp = nx.approximation.simulated_annealing_tsp
      >>> method = lambda G, weight: SA_tsp(G, "greedy", weight=weight, temp=500)
      >>> path = tsp(G, cycle=False, method=method)
      >>> path in ([4, 3, 2, 1, 0, 8, 7, 6, 5], [5, 6, 7, 8, 0, 1, 2, 3, 4])
      True

  Otherwise, pass other keyword arguments directly into the tsp function.

      >>> path = tsp(
      ...     G,
      ...     cycle=False,
      ...     method=nx.approximation.simulated_annealing_tsp,
      ...     init_cycle="greedy",
      ...     temp=500,
      ... )
      >>> path in ([4, 3, 2, 1, 0, 8, 7, 6, 5], [5, 6, 7, 8, 0, 1, 2, 3, 4])
      True