# 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:

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(2)

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

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

In FindShortestTour, rules are taken to be undirected edges:

## 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:

Wolfram Research (2007), FindShortestTour, Wolfram Language function, https://reference.wolfram.com/language/ref/FindShortestTour.html (updated 2015).

#### Text

Wolfram Research (2007), FindShortestTour, Wolfram Language function, https://reference.wolfram.com/language/ref/FindShortestTour.html (updated 2015).

#### CMS

Wolfram Language. 2007. "FindShortestTour." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindShortestTour.html.

#### APA

Wolfram Language. (2007). FindShortestTour. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindShortestTour.html

#### BibTeX

@misc{reference.wolfram_2024_findshortesttour, author="Wolfram Research", title="{FindShortestTour}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindShortestTour.html}", note=[Accessed: 29-May-2024 ]}

#### BibLaTeX

@online{reference.wolfram_2024_findshortesttour, organization={Wolfram Research}, title={FindShortestTour}, year={2015}, url={https://reference.wolfram.com/language/ref/FindShortestTour.html}, note=[Accessed: 29-May-2024 ]}