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

  • 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:
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
On this page