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 nodesThis 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 andasadpour_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
isFalse
, 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 graphG
includes edges with weights that do not adhere to the triangle inequality, such as whenG
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 inputsG
, andweight
; and return a list of nodes along the cycle.Provided options include
christofides()
,greedy_tsp()
,simulated_annealing_tsp()
andthreshold_accepting_tsp()
.If
method is None
: usechristofides()
for undirectedG
andasadpour_atsp()
for directedG
.- **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 throughnodes
.
- 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