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 forms All an association giving element, index and distance - 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 allBasic Examples (3)
Scope (7)
FindShortestTour works with a list of points:
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)
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:
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