--- title: "FindShortestTour" language: "en" type: "Symbol" summary: "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[{v -> w, ...}, ...] uses rules v -> w to specify the graph g. FindShortestTour[data -> prop, ...] gives the property prop for data." keywords: - circuit - closed directed walk - closed walk - combinatorial optimization - FindShortestPath - graph cycle - shortest circuit - shortest cycle - simple cycle - traveling salesman problem - TSP canonical_url: "https://reference.wolfram.com/language/ref/FindShortestTour.html" source: "Wolfram Language Documentation" related_guides: - title: "Optimization" link: "https://reference.wolfram.com/language/guide/Optimization.en.md" - title: "Paths, Cycles, and Flows" link: "https://reference.wolfram.com/language/guide/GraphPathsCyclesAndFlows.en.md" - title: "Discrete Mathematics" link: "https://reference.wolfram.com/language/guide/DiscreteMathematics.en.md" - title: "Computational Geometry" link: "https://reference.wolfram.com/language/guide/ComputationalGeometry.en.md" - title: "Distance and Similarity Measures" link: "https://reference.wolfram.com/language/guide/DistanceAndSimilarityMeasures.en.md" related_functions: - title: "FindHamiltonianCycle" link: "https://reference.wolfram.com/language/ref/FindHamiltonianCycle.en.md" - title: "FindHamiltonianPath" link: "https://reference.wolfram.com/language/ref/FindHamiltonianPath.en.md" - title: "FindShortestPath" link: "https://reference.wolfram.com/language/ref/FindShortestPath.en.md" - title: "FindPath" link: "https://reference.wolfram.com/language/ref/FindPath.en.md" - title: "FindPostmanTour" link: "https://reference.wolfram.com/language/ref/FindPostmanTour.en.md" - title: "FindEulerianCycle" link: "https://reference.wolfram.com/language/ref/FindEulerianCycle.en.md" - title: "FindMinimum" link: "https://reference.wolfram.com/language/ref/FindMinimum.en.md" - title: "NMinimize" link: "https://reference.wolfram.com/language/ref/NMinimize.en.md" - title: "Nearest" link: "https://reference.wolfram.com/language/ref/Nearest.en.md" - title: "FindCurvePath" link: "https://reference.wolfram.com/language/ref/FindCurvePath.en.md" --- # 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[{v -> w, …}, …] uses rules v -> w to specify the graph g. FindShortestTour[data -> prop, …] 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. [image] * In ``FindShortestTour[data -> prop, …]``, 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 (21) ### Basic Examples (3) Find the length and ordering of the shortest tour through points in the plane: ```wl In[1]:= 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}}; In[2]:= FindShortestTour[%] Out[2]= {14 + 5 Sqrt[2], {1, 6, 9, 13, 16, 17, 18, 19, 14, 10, 7, 11, 15, 12, 8, 5, 4, 3, 2, 1}} ``` Order the points according to the tour found: ```wl In[3]:= pts[[Last[%]]] Out[3]= {{1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}, {5, 2}, {5, 3}, {5, 4}, {4, 3}, {3, 2}, {2, 3}, {3, 4}, {4, 5}, {3, 5}, {2, 5}, {1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}} ``` Plot the tour: ```wl In[4]:= Graphics[Line[%]] Out[4]= [image] ``` --- Find the shortest tour in a graph: ```wl In[1]:= g = PolyhedronData["Dodecahedron", "Skeleton"]; In[2]:= FindShortestTour[g] Out[2]= {20, {1, 15, 10, 18, 13, 2, 5, 11, 12, 6, 20, 4, 8, 16, 7, 3, 19, 17, 9, 14, 1}} ``` Highlight the tour: ```wl In[3]:= HighlightGraph[g, PathGraph[%[[2]]]] Out[3]= [image] ``` --- Find a shortest tour of Europe from Albania to Spain: ```wl In[1]:= FindShortestTour[CountryData["Europe"] -> "Elements", Entity["Country", "Albania"], Entity["Country", "Spain"]] Out[1]= {Entity["Country", "Albania"], Entity["Country", "Macedonia"], Entity["Country", "Kosovo"], Entity["Country", "Serbia"], Entity["Country", "Montenegro"], Entity["Country", "BosniaHerzegovina"], Entity["Country", "Croatia"], Entity["Country", "Slove ... fMan"], Entity["Country", "Ireland"], Entity["Country", "Guernsey"], Entity["Country", "Jersey"], Entity["Country", "France"], Entity["Country", "Andorra"], Entity["Country", "Gibraltar"], Entity["Country", "Portugal"], Entity["Country", "Spain"]} ``` Show the tour: ```wl In[2]:= GeoGraphics[{Thick, Red, GeoPath[%]}] Out[2]= [image] ``` ### Scope (7) ``FindShortestTour`` works with a list of points: ```wl In[1]:= FindShortestTour[{{2, 2}, {5, 2}, {5, 3}, {4, 5}, {4, 4}, {3, 2}}] Out[1]= {5 + Sqrt[2] + Sqrt[13], {1, 4, 5, 3, 2, 6, 1}} ``` --- A list of strings: ```wl In[1]:= FindShortestTour[{"cat", "dog", "do", "cap", "dock"}] Out[1]= {11, {1, 5, 3, 2, 4, 1}} ``` --- A list of geodetic positions: ```wl In[1]:= FindShortestTour[{GeoPosition[{41, 20}], GeoPosition[{5, 20}], GeoPosition[{49, 32}], GeoPosition[{53, 28}], GeoPosition[{47, 29}]}] Out[1]= {Quantity[6852.02, "Miles"], {1, 2, 5, 3, 4, 1}} ``` --- Undirected graphs: ```wl In[1]:= FindShortestTour[[image]] Out[1]= {12, {1, 2, 3, 6, 9, 12, 11, 10, 7, 8, 5, 4, 1}} ``` --- Weighted graphs: ```wl In[1]:= FindShortestTour[[image]] Out[1]= {2.22, {1, 2, 3, 4, 1}} ``` --- Use rules to specify the graph: ```wl In[1]:= 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}] Out[1]= {12, {1, 4, 7, 10, 11, 12, 9, 8, 5, 6, 3, 2, 1}} ``` --- ``FindShortestTour`` works with large graphs: ```wl In[1]:= g = RandomGraph[{1000, 5000}]; In[2]:= Timing[FindShortestTour[g]]//Short Out[2]//Short= {28.485783, {1000, {«1»}}} ``` ### Options (3) #### DistanceFunction (3) By default, ``EditDistance`` is used for strings: ```wl In[1]:= FindShortestTour[{"This", "finds", "the", "shortest", "tour", "through", "a", "list", "of", "strings"}] Out[1]= {38, {1, 8, 2, 10, 4, 6, 5, 9, 7, 3, 1}} In[2]:= {"This", "finds", "the", "shortest", "tour", "through", "a", "list", "of", "strings"}[[%[[2]]]] Out[2]= {"This", "list", "finds", "strings", "shortest", "through", "tour", "of", "a", "the", "This"} ``` --- This finds the shortest tour through 100 points, with a penalty added to cross a "river": ```wl In[1]:= pts = RandomReal[1, {100, 2}]; In[2]:= {len, tour} = FindShortestTour[pts, DistanceFunction -> ((If[(#1[[1]] ≤ .5 && #2[[1]] ≥ .5) || (#2[[1]] ≤ .5 && #1[[1]] ≥ .5), 100000, EuclideanDistance[#1, #2]])&)] Out[2]= {200007., {1, 90, 66, 98, 30, 73, 26, 45, 48, 99, 34, 8, 68, 84, 88, 52, 55, 35, 69, 40, 63, 95, 77, 15, 41, 25, 6, 80, 23, 79, 85, 17, 92, 7, 58, 91, 71, 31, 14, 2, 78, 57, 28, 37, 59, 83, 53, 4, 36, 29, 61, 75, 24, 20, 43, 46, 97, 96, 21, 67, 89, 27, 86, 16, 18, 93, 38, 39, 13, 9, 33, 12, 54, 44, 76, 49, 19, 94, 81, 47, 10, 100, 51, 72, 62, 32, 70, 64, 74, 22, 60, 11, 56, 3, 50, 87, 65, 42, 5, 82, 1}} ``` This plots the tour with the "river" in red: ```wl In[3]:= Graphics[{GraphicsComplex[pts, {Point[Range[100]], Line[tour]}], Red, Line[{{0.5, 0}, {0.5, 1}}]}, Frame -> True, FrameTicks -> Automatic] Out[3]= [image] ``` --- This defines a sparse distance matrix among six points and finds the shortest tour: ```wl In[1]:= 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]; In[2]:= {len, tour} = FindShortestTour[{1, 2, 3, 4, 5, 6}, DistanceFunction -> (d[[#1, #2]]&)] Out[2]= {6, {1, 4, 3, 5, 2, 6, 1}} ``` This plots the shortest tour in red, and the distance on each edge: ```wl In[3]:= HighlightGraph[WeightedAdjacencyGraph[d, EdgeLabels -> "EdgeWeight"], PathGraph[tour]] Out[3]= [image] ``` ### Applications (3) Find the shortest tour visiting random points in the plane: ```wl In[1]:= p = RandomReal[10, {50, 2}]; In[2]:= FindShortestTour[p] Out[2]= {58.6734, {1, 23, 43, 3, 24, 21, 31, 39, 17, 6, 29, 16, 42, 22, 27, 11, 35, 12, 44, 4, 28, 47, 37, 33, 49, 36, 40, 48, 8, 19, 45, 46, 20, 9, 25, 50, 18, 32, 30, 34, 15, 2, 10, 41, 26, 14, 38, 13, 5, 7, 1}} ``` Show the tour: ```wl In[3]:= Graphics[{Line[p[[Last[%]]]], PointSize[Medium], Red, Point[p]}] Out[3]= [image] ``` The shortest tour visiting random points in 3D: ```wl In[4]:= p = RandomReal[20, {100, 3}]; In[5]:= FindShortestTour[p]; In[6]:= Graphics3D[{Line[p[[Last[%]]]], Sphere[p, 0.5]}] Out[6]= [image] ``` --- Find a traveling salesman tour of Europe: ```wl In[1]:= europe = CountryData["Europe"] Out[1]= {Entity["Country", "Albania"], Entity["Country", "Andorra"], Entity["Country", "Austria"], Entity["Country", "Belarus"], Entity["Country", "Belgium"], Entity["Country", "BosniaHerzegovina"], Entity["Country", "Bulgaria"], Entity["Country", "Croatia ... y["Country", "Slovenia"], Entity["Country", "Spain"], Entity["Country", "Svalbard"], Entity["Country", "Sweden"], Entity["Country", "Switzerland"], Entity["Country", "Ukraine"], Entity["Country", "UnitedKingdom"], Entity["Country", "VaticanCity"]} ``` Latitude and longitude of geographical centers: ```wl In[2]:= pos = GeoPosition[CountryData[#, "CenterCoordinates"]]& /@ europe; In[3]:= FindShortestTour[europe]; ``` Show the tour: ```wl In[4]:= GeoGraphics[{Thick, Red, GeoPath[pos[[Last[%]]]]}] Out[4]= [image] ``` --- Draw Leonardo da Vinci’s *Mona Lisa* as a continuous-line drawing: ```wl In[1]:= monalisa = [image]; ``` Convert the image to points: ```wl In[2]:= monalisa = ColorQuantize[ColorConvert[monalisa, "Grayscale"], 2]; In[3]:= pos = PixelValuePositions[ImageAdjust[monalisa], 0]; ``` Draw *Mona Lisa:* ```wl In[4]:= res = FindShortestTour[pos]; In[5]:= Graphics[Line[pos[[res[[2]]]]]] Out[5]= [image] ``` ### Properties & Relations (2) ``FindShortestTour`` gives an empty list for non-Hamiltonian graphs: ```wl In[1]:= g = GraphData[{"CayleyTree", {3, 4}}] Out[1]= [image] In[2]:= HamiltonianGraphQ[g] Out[2]= False In[3]:= FindShortestTour[g] Out[3]= {} ``` --- A graph with no shortest tour may have a shortest path visiting every vertex: ```wl In[1]:= g = [image]; In[2]:= FindShortestTour[g] Out[2]= {} In[3]:= FindHamiltonianPath[g] Out[3]= {7, 8, 10, 13, 12, 11, 9, 6, 4, 1, 2, 3, 5} ``` ### Possible Issues (2) For large datasets, ``FindShortestTour`` finds a tour whose length is at least close to the minimum: ```wl In[1]:= data = RandomInteger[100, {1000, 2}]; In[2]:= FindShortestTour[data]//Short Out[2]//Short= {661 + 296 Sqrt[2] + 253 Sqrt[5] + 91 Sqrt[10] + 39 Sqrt[13] + 35 Sqrt[17] + 10 Sqrt[26] + 5 Sqrt[29] + 2 Sqrt[34] + Sqrt[37] + 2 Sqrt[41] + 2 Sqrt[53], {1, «1000»}} In[3]:= N[%[[1]]] Out[3]= 2341.05 ``` Use ``PerformanceGoal -> "Quality"`` to find an optimal result: ```wl In[4]:= FindShortestTour[data, PerformanceGoal :> "Quality"]//Short Out[4]//Short= {645 + 297 Sqrt[2] + 249 Sqrt[5] + 94 Sqrt[10] + 40 Sqrt[13] + 28 Sqrt[17] + 11 Sqrt[26] + 9 Sqrt[29] + 3 Sqrt[34] + 2 Sqrt[37] + 2 Sqrt[41] + Sqrt[53], {1, «1000»}} In[5]:= N[%[[1]]] Out[5]= 2333.03 ``` --- In ``FindShortestTour``, rules are taken to be undirected edges: ```wl In[1]:= 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}; In[2]:= FindShortestTour[rules] Out[2]= {12, {1, 4, 7, 10, 11, 12, 9, 8, 5, 6, 3, 2, 1}} In[3]:= FindShortestTour[Graph[rules, DirectedEdges -> False]] Out[3]= {12, {1, 3, 7, 10, 11, 12, 9, 8, 5, 6, 4, 2, 1}} ``` ### Neat Examples (1) Plan a tour through every country of the world: ```wl In[1]:= places = CountryData["Countries"]; In[2]:= centers = Map[GeoPosition[CountryData[#, "CenterCoordinates"]]&, places]; In[3]:= {dist, route} = FindShortestTour[centers]; ``` Use an azimuthal projection to visualize the tour: ```wl In[4]:= GeoGraphics[GeoPath[centers[[route]]], GeoRange -> "World"] Out[4]= [image] ``` Visualize the tour on a spherical Earth: ```wl In[5]:= r = 6371830; In[6]:= countryCenters = Map[First[GeoPositionXYZ[#]]&, centers[[route]]]; In[7]:= arc[x_, y_] := Module[{a}, a = VectorAngle[x, y]; Table[Evaluate[RotationTransform[θ, {x, y}][x]], {θ, 0, a, a / Ceiling[10a]}]] In[8]:= tourLine = Apply[arc, Partition[countryCenters, 2, 1], {1}]; In[9]:= countries = MapThread[Tooltip[Point[#1], #2[[2]]]&, {countryCenters, places[[route]]}]; In[10]:= Graphics3D[{Sphere[{0, 0, 0}, 0.99 r], {Red, Thick, Line[tourLine]}, {Yellow, PointSize[Medium], countries}}, Boxed -> False, SphericalRegion -> True] Out[10]= [image] ``` ## See Also * [`FindHamiltonianCycle`](https://reference.wolfram.com/language/ref/FindHamiltonianCycle.en.md) * [`FindHamiltonianPath`](https://reference.wolfram.com/language/ref/FindHamiltonianPath.en.md) * [`FindShortestPath`](https://reference.wolfram.com/language/ref/FindShortestPath.en.md) * [`FindPath`](https://reference.wolfram.com/language/ref/FindPath.en.md) * [`FindPostmanTour`](https://reference.wolfram.com/language/ref/FindPostmanTour.en.md) * [`FindEulerianCycle`](https://reference.wolfram.com/language/ref/FindEulerianCycle.en.md) * [`FindMinimum`](https://reference.wolfram.com/language/ref/FindMinimum.en.md) * [`NMinimize`](https://reference.wolfram.com/language/ref/NMinimize.en.md) * [`Nearest`](https://reference.wolfram.com/language/ref/Nearest.en.md) * [`FindCurvePath`](https://reference.wolfram.com/language/ref/FindCurvePath.en.md) ## Related Guides * [`Optimization`](https://reference.wolfram.com/language/guide/Optimization.en.md) * [Paths, Cycles, and Flows](https://reference.wolfram.com/language/guide/GraphPathsCyclesAndFlows.en.md) * [Discrete Mathematics](https://reference.wolfram.com/language/guide/DiscreteMathematics.en.md) * [Computational Geometry](https://reference.wolfram.com/language/guide/ComputationalGeometry.en.md) * [Distance and Similarity Measures](https://reference.wolfram.com/language/guide/DistanceAndSimilarityMeasures.en.md) ## History * [Introduced in 2007 (6.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn60.en.md) \| [Updated in 2014 (10.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn100.en.md) ▪ [2015 (10.2)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn102.en.md) ▪ [2015 (10.3)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn103.en.md) ▪ [2024 (14.1)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn141.en.md)