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.
FindShortestTour [dataprop,…]
gives the property prop for data.
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.
FindShortestTour [dataprop,…]
gives the property prop for data.
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.
- In FindShortestTour [dataprop,…], possible forms for prop include:
-
"Elements" the element of the shortest tour"Indices" the indices of the shortest tour"Length" the distance of the shortest tour{prop1,prop2,…} a list of multiple formsAll an association giving element, index and distance
- The following options can be given:
-
- Automatic settings for DistanceFunction depending on the vi include:
-
EuclideanDistance numbers of lists of numbersEditDistance stringsGeoDistance 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 allBasic 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 Vinci’s 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:
See Also
FindHamiltonianCycle FindHamiltonianPath FindShortestPath FindPath FindPostmanTour FindEulerianCycle FindMinimum NMinimize Nearest FindCurvePath
Function Repository: VoronoiCellTours
Related Guides
History
Introduced in 2007 (6.0) | Updated in 2014 (10.0) ▪ 2015 (10.2) ▪ 2015 (10.3) ▪ 2024 (14.1)
Text
Wolfram Research (2007), FindShortestTour, Wolfram Language function, https://reference.wolfram.com/language/ref/FindShortestTour.html (updated 2024).
CMS
Wolfram Language. 2007. "FindShortestTour." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2024. 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_2025_findshortesttour, author="Wolfram Research", title="{FindShortestTour}", year="2024", howpublished="\url{https://reference.wolfram.com/language/ref/FindShortestTour.html}", note=[Accessed: 05-December-2025]}
BibLaTeX
@online{reference.wolfram_2025_findshortesttour, organization={Wolfram Research}, title={FindShortestTour}, year={2024}, url={https://reference.wolfram.com/language/ref/FindShortestTour.html}, note=[Accessed: 05-December-2025]}