# FindShortestTour

FindShortestTour[{v1,v2,}]

attempts to find an ordering of the vi that minimizes the total distance on a tour that visits all the vi once.

FindShortestTour[graph]

attempts to find an ordering of the vertices in graph that minimizes the total length when visiting each vertex once.

FindShortestTour[{v1,v2,},j,k]

finds an ordering of the vi that minimizes the total distance on a path from vj to vk.

FindShortestTour[graph,s,t]

finds an ordering of the vertices that minimizes the total length on a path from s to t.

FindShortestTour[{vw,},]

uses rules vw to specify the graph g.

# Details and Options

• FindShortestTour is also known as the traveling salesman problem (TSP).
• FindShortestTour returns a list of the form {dmin,{vi1,vi2,}}, where dmin is the length of the tour found, and {vi1,vi2,} is the ordering.
• The following options can be given:
•  DistanceFunction Automatic function to apply to pairs of objects Method Automatic method to use
• Automatic settings for DistanceFunction depending on the vi include:
•  EuclideanDistance numbers of lists of numbers EditDistance strings GeoDistance geo positions
• For graph, the distance is taken to be GraphDistance, which is the shortest path length for an unweighted graph and the sum of weights for a weighted graph.

# Examples

open allclose all

## Basic Examples(3)

Find the length and ordering of the shortest tour through points in the plane:

 In[1]:=
 In[2]:=
 Out[2]=

Order the points according to the tour found:

 In[3]:=
 Out[3]=

Plot the tour:

 In[4]:=
 Out[4]=

Find the shortest tour in a graph:

 In[1]:=
 In[2]:=
 Out[2]=

Highlight the tour:

 In[3]:=
 Out[3]=

Find a shortest tour of Europe from Albania to Spain:

 In[1]:=
 In[2]:=
 In[3]:=
 In[4]:=
 Out[4]=

Show the tour:

 In[5]:=
 Out[5]=