traveling_salesman_problem#

traveling_salesman_problem(G, weight='weight', nodes=None, cycle=True, method=None, **kwargs)[source]#

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

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:
GNetworkX graph

A possibly weighted graph

nodescollection of nodes (default=G.nodes)

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

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.

cyclebool (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.

methodfunction (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`.

**kwargsdict

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
```