# 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 all close all

## Basic Examples(3)

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

 In:= In:= Out= Order the points according to the tour found:

 In:= Out= Plot the tour:

 In:= Out= Find the shortest tour in a graph:

 In:= In:= Out= Highlight the tour:

 In:= Out= Find a shortest tour of Europe from Albania to Spain:

 In:= In:= In:= In:= Out= Show the tour:

 In:= Out= ## Neat Examples(1)

Introduced in 2007
(6.0)
|
Updated in 2015
(10.3)