a connected (di)graph
(optional) a Matrix containing edge weights
The TravelingSalesman command returns two objects, w of type numeric and the second C a list which is a permutation of the vertices The first output is the optimal value for the traveling salesman problem, and the second is a Hamiltonian cycle that achieves the optimal value.
The algorithm is a branch-and-bound algorithm using the Reduce bound (see Kreher and Stinson, 1999).
If a second argument is specified, it is used for the weights. If an edge from vertex u to v is not in G then, regardless of the edge weight in M, it is treated as infinity.
If G is not a weighted graph then the adjacency matrix of G is used for the edge weights.
G ≔ Graph⁡1,2,2,2,3,2,3,4,2,4,1,2
G≔Graph 1: an undirected weighted graph with 4 vertices and 4 edge(s)
Graph 1: an undirected weighted graph with 4 vertices and 6 edge(s)
w,tour ≔ TravelingSalesman⁡G
G ≔ CompleteGraph⁡10:
M ≔ Matrix⁡0,68,37,95,57,30,1,25,71,84,68,0,9,26,90,26,97,29,47,78,37,9,0,84,59,11,67,61,75,35,95,26,84,0,1,99,55,63,19,8,57,90,59,1,0,61,66,18,7,48,30,26,11,99,61,0,93,10,14,54,1,97,67,55,66,93,0,47,20,95,25,29,61,63,18,10,47,0,28,52,71,47,75,19,7,14,20,28,0,92,84,78,35,8,48,54,95,52,92,0:
Download Help Document
What kind of issue would you like to report? (Optional)