WOLFRAM

Wolfram Language & System Documentation Center

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
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Options  
DistanceFunction  
Applications  
Properties & Relations  
Possible Issues  
Neat Examples  
See Also
Related Guides
History
Cite this Page

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
    Allan association giving element, index and distance
  • The following options can be given:
  • DistanceFunction Automaticfunction to apply to pairs of objects
    MethodAutomaticmethod to use
  • Automatic settings for DistanceFunction depending on the vi include:
  • EuclideanDistancenumbers of lists of numbers
    EditDistancestrings
    GeoDistancegeo 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:

Wolfram Language code: pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, 5}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 1}, {5, 2}, {5, 3}, {5, 4}};
Wolfram Language code: FindShortestTour[%]

Order the points according to the tour found:

Wolfram Language code: pts[[Last[%]]]

Plot the tour:

Wolfram Language code: Graphics[Line[%]]

Shortest tour starting at the first point and ending at the fifth point:

Wolfram Language code: FindShortestTour[pts, 1, 5]

Plot the tour:

Wolfram Language code: Graphics[Line[pts[[Last[%]]]]]

Find the shortest tour in a graph:

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"];
Wolfram Language code: FindShortestTour[g]

Highlight the tour:

Wolfram Language code: HighlightGraph[g, PathGraph[%[[2]]]]

Find a shortest tour of Europe from Albania to Spain:

Wolfram Language code: FindShortestTour[CountryData["Europe"] -> "Elements", Entity["Country", "Albania"], Entity["Country", "Spain"]]

Show the tour:

Wolfram Language code: GeoGraphics[{Thick, Red, GeoPath[%]}]

Scope  (7)

FindShortestTour works with a list of points:

Wolfram Language code: FindShortestTour[{{2, 2}, {5, 2}, {5, 3}, {4, 5}, {4, 4}, {3, 2}}]

A list of strings:

Wolfram Language code: FindShortestTour[{"cat", "dog", "do", "cap", "dock"}]

A list of geodetic positions:

Wolfram Language code: FindShortestTour[{GeoPosition[{41, 20}], GeoPosition[{5, 20}], GeoPosition[{49, 32}], GeoPosition[{53, 28}], GeoPosition[{47, 29}]}]

Undirected graphs:

Wolfram Language code: FindShortestTour[[image]]

Weighted graphs:

Wolfram Language code: FindShortestTour[[image]]

Use rules to specify the graph:

Wolfram Language code: FindShortestTour[{1 -> 2, 1 -> 4, 2 -> 3, 2 -> 5, 3 -> 6, 4 -> 5, 4 -> 7, 5 -> 6, 5 -> 8, 6 -> 9, 7 -> 8, 7 -> 10, 8 -> 9, 8 -> 11, 9 -> 12, 10 -> 11, 11 -> 12}]

FindShortestTour works with large graphs:

Wolfram Language code: g = RandomGraph[{1000, 5000}];
Wolfram Language code: Timing[FindShortestTour[g]]//Short

Options  (3)

DistanceFunction  (3)

By default, EditDistance is used for strings:

Wolfram Language code: FindShortestTour[{"This", "finds", "the", "shortest", "tour", "through", "a", "list", "of", "strings"}]
Wolfram Language code: {"This", "finds", "the", "shortest", "tour", "through", "a", "list", "of", "strings"}[[%[[2]]]]

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

Wolfram Language code: pts = RandomReal[1, {100, 2}];
Wolfram Language code: {len, tour} = FindShortestTour[pts, DistanceFunction -> ((If[(#1[[1]] ≤ .5 && #2[[1]] ≥ .5) || (#2[[1]] ≤ .5 && #1[[1]] ≥ .5), 100000, EuclideanDistance[#1, #2]])&)]

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

Wolfram Language code: Graphics[{GraphicsComplex[pts, {Point[Range[100]], Line[tour]}], Red, Line[{{0.5, 0}, {0.5, 1}}]}, Frame -> True, FrameTicks -> Automatic]

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

Wolfram Language code: d = SparseArray[{{1, 2} -> 1, {2, 1} -> 1, {6, 1} -> 1, {6, 2} -> 1, {5, 1} -> 1, {1, 5} -> 1, {2, 6} -> 1, {2, 3} -> 10, {3, 2} -> 10, {3, 5} -> 1, {5, 3} -> 1, {3, 4} -> 1, {4, 3} -> 1, {4, 5} -> 15, {4, 1} -> 1, {5, 4} -> 15, {5, 2} -> 1, {1, 4} -> 1, {2, 5} -> 1, {1, 6} -> 1}, {6, 6}, Infinity];
Wolfram Language code: {len, tour} = FindShortestTour[{1, 2, 3, 4, 5, 6}, DistanceFunction -> (d[[#1, #2]]&)]

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

Wolfram Language code: HighlightGraph[WeightedAdjacencyGraph[d, EdgeLabels -> "EdgeWeight"], PathGraph[tour]]

Applications  (3)

Find the shortest tour visiting random points in the plane:

Wolfram Language code: p = RandomReal[10, {50, 2}];
Wolfram Language code: FindShortestTour[p]

Show the tour:

Wolfram Language code: Graphics[{Line[p[[Last[%]]]], PointSize[Medium], Red, Point[p]}]

The shortest tour visiting random points in 3D:

Wolfram Language code: p = RandomReal[20, {100, 3}];
Wolfram Language code: FindShortestTour[p];
Wolfram Language code: Graphics3D[{Line[p[[Last[%]]]], Sphere[p, 0.5]}]

Find a traveling salesman tour of Europe:

Wolfram Language code: europe = CountryData["Europe"]

Latitude and longitude of geographical centers:

Wolfram Language code: pos = GeoPosition[CountryData[#, "CenterCoordinates"]]& /@ europe;
Wolfram Language code: FindShortestTour[europe];

Show the tour:

Wolfram Language code: GeoGraphics[{Thick, Red, GeoPath[pos[[Last[%]]]]}]

Draw Leonardo da Vinci’s Mona Lisa as a continuous-line drawing:

Wolfram Language code: monalisa = [image];

Convert the image to points:

Wolfram Language code: monalisa = ColorQuantize[ColorConvert[monalisa, "Grayscale"], 2];
Wolfram Language code: pos = PixelValuePositions[ImageAdjust[monalisa], 0];

Draw Mona Lisa:

Wolfram Language code: res = FindShortestTour[pos];
Wolfram Language code: Graphics[Line[pos[[res[[2]]]]]]

Properties & Relations  (2)

FindShortestTour gives an empty list for non-Hamiltonian graphs:

Wolfram Language code: g = GraphData[{"CayleyTree", {3, 4}}]
Wolfram Language code: HamiltonianGraphQ[g]
Wolfram Language code: FindShortestTour[g]

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

Wolfram Language code: g = [image];
Wolfram Language code: FindShortestTour[g]
Wolfram Language code: FindHamiltonianPath[g]

Possible Issues  (2)

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

Wolfram Language code: data = RandomInteger[100, {1000, 2}];
Wolfram Language code: FindShortestTour[data]//Short
Wolfram Language code: N[%[[1]]]

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

Wolfram Language code: FindShortestTour[data, PerformanceGoal :> "Quality"]//Short
Wolfram Language code: N[%[[1]]]

In FindShortestTour, rules are taken to be undirected edges:

Wolfram Language code: rules = {1 -> 2, 1 -> 4, 2 -> 3, 2 -> 5, 3 -> 6, 4 -> 5, 4 -> 7, 5 -> 6, 5 -> 8, 6 -> 9, 7 -> 8, 7 -> 10, 8 -> 9, 8 -> 11, 9 -> 12, 10 -> 11, 11 -> 12};
Wolfram Language code: FindShortestTour[rules]
Wolfram Language code: FindShortestTour[Graph[rules, DirectedEdges -> False]]

Neat Examples  (1)

Plan a tour through every country of the world:

Wolfram Language code: places = CountryData["Countries"];
Wolfram Language code: centers = Map[GeoPosition[CountryData[#, "CenterCoordinates"]]&, places];
Wolfram Language code: {dist, route} = FindShortestTour[centers];

Use an azimuthal projection to visualize the tour:

Wolfram Language code: GeoGraphics[GeoPath[centers[[route]]], GeoRange -> "World"]

Visualize the tour on a spherical Earth:

Wolfram Language code: r = 6371830;
Wolfram Language code: countryCenters = Map[First[GeoPositionXYZ[#]]&, centers[[route]]];
Wolfram Language code: arc[x_, y_] := Module[{a}, a = VectorAngle[x, y]; Table[Evaluate[RotationTransform[θ, {x, y}][x]], {θ, 0, a, a / Ceiling[10a]}]]
Wolfram Language code: tourLine = Apply[arc, Partition[countryCenters, 2, 1], {1}];
Wolfram Language code: countries = MapThread[Tooltip[Point[#1], #2[[2]]]&, {countryCenters, places[[route]]}];
Wolfram Language code: Graphics3D[{Sphere[{0, 0, 0}, 0.99 r], {Red, Thick, Line[tourLine]}, {Yellow, PointSize[Medium], countries}}, Boxed -> False, SphericalRegion -> True]
Wolfram Research (2007), FindShortestTour, Wolfram Language function, https://reference.wolfram.com/language/ref/FindShortestTour.html (updated 2024).

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_2026_findshortesttour, author="Wolfram Research", title="{FindShortestTour}", year="2024", howpublished="\url{https://reference.wolfram.com/language/ref/FindShortestTour.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_findshortesttour, organization={Wolfram Research}, title={FindShortestTour}, year={2024}, url={https://reference.wolfram.com/language/ref/FindShortestTour.html}, note=[Accessed: 12-June-2026]}