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.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{Graph}\left(\left\{\left[\left\{1\,2\right\}\,2\right]\,\left[\left\{1\,4\right\}\,2\right]\,\left[\left\{2\,3\right\}\,2\right]\,\left[\left\{3\,4\right\}\,2\right]\right\}\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; weighted\; graph\; with\; 4\; vertices\; and\; 4\; edge(s)}$

$\mathrm{TravelingSalesman}\left(G\right)$

$8,\left[1\,2\,3\,4\,1\right]$

$\mathrm{AddEdge}\left(G\,\left\{\left[\left\{1\,3\right\}\,1\right]\,\left[\left\{2\,4\right\}\,1\right]\right\}\right)$

$\mathrm{Graph\; 1:\; an\; undirected\; weighted\; graph\; with\; 4\; vertices\; and\; 6\; edge(s)}$

$\mathrm{DrawGraph}\left(G\,\mathrm{style}=\mathrm{circle}\right)$

$w,\mathrm{tour}≔\mathrm{TravelingSalesman}\left(G\right)$

$w,\mathrm{tour}≔6,\left[1\,2\,4\,3\,1\right]$

$\mathrm{HighlightTrail}\left(G\,\mathrm{tour}\,\mathrm{red}\right)$

$\mathrm{DrawGraph}\left(G\,\mathrm{style}=\mathrm{circle}\right)$

$G≔\mathrm{CompleteGraph}\left(10\right)\:$

$M≔\mathrm{Matrix}\left(\left[\left[0\,68\,37\,95\,57\,30\,1\,25\,71\,84\right]\,\left[68\,0\,9\,26\,90\,26\,97\,29\,47\,78\right]\,\left[37\,9\,0\,84\,59\,11\,67\,61\,75\,35\right]\,\left[95\,26\,84\,0\,1\,99\,55\,63\,19\,8\right]\,\left[57\,90\,59\,1\,0\,61\,66\,18\,7\,48\right]\,\left[30\,26\,11\,99\,61\,0\,93\,10\,14\,54\right]\,\left[1\,97\,67\,55\,66\,93\,0\,47\,20\,95\right]\,\left[25\,29\,61\,63\,18\,10\,47\,0\,28\,52\right]\,\left[71\,47\,75\,19\,7\,14\,20\,28\,0\,92\right]\,\left[84\,78\,35\,8\,48\,54\,95\,52\,92\,0\right]\right]\right)\:$

$\mathrm{TravelingSalesman}\left(G\,M\right)$

$142,\left[1\,8\,6\,2\,3\,10\,4\,5\,9\,7\,1\right]$