traveling_salesman_problem

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

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.

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 threshold_accepting_tsp() for directed G.

To specify parameters for these provided functions, construct lambda functions that state the specific value. method must have 2 inputs. (See examples).

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

Build (curry) your own function to provide parameter values to the methods.

>>> SA_tsp = nx.approximation.simulated_annealing_tsp
>>> method = lambda G, wt: SA_tsp(G, "greedy", weight=wt, 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