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

Examples

open allclose all

Basic Examples  (3)

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

Order the points according to the tour found:

Plot the tour:

Find the shortest tour in a graph:

Highlight the tour:

Find a shortest tour of Europe from Albania to Spain:

Show the tour:

Scope  (7)

FindShortestTour works with a list of points:

A list of strings:

A list of geodetic positions:

Undirected graphs:

Weighted graphs:

Use rules to specify the graph:

FindShortestTour works with large graphs:

Options  (3)

DistanceFunction  (3)

By default, EditDistance is used for strings:

This finds the shortest tour through 100 points, with a penalty added to cross a "river":

This plots the tour with the "river" in red:

This defines a sparse distance matrix among six points and finds the shortest tour:

This plots the shortest tour in red, and the distance on each edge:

Applications  (3)

Find the shortest tour visiting random points in the plane:

Show the tour:

The shortest tour visiting random points in 3D:

Find a traveling salesman tour of Europe:

Latitude and longitude of geographical centers:

Show the tour:

Draw Leonardo da Vincis Mona Lisa as a continuous-line drawing:

Convert the image to points:

Draw Mona Lisa:

Properties & Relations  (2)

FindShortestTour gives an empty list for non-Hamiltonian graphs:

A graph with no shortest tour may have a shortest path visiting every vertex:

Possible Issues  (1)

For large datasets, FindShortestTour finds a tour whose length is at least close to the minimum:

Use PerformanceGoal->"Quality" to find an optimal result:

Neat Examples  (1)

Plan a tour through every country of the world:

Use an azimuthal projection to visualize the tour:

Visualize the tour on a spherical Earth:

Introduced in 2007
 (6.0)
 |
Updated in 2014
 (10.0)
2015
 (10.2)
2015
 (10.3)