WOLFRAM

Wolfram Language & System Documentation Center

FindHamiltonianPath[g]

finds a Hamiltonian path in the graph g with the smallest total length.

FindHamiltonianPath[g,s,t]

finds a Hamiltonian path with the smallest total length from s to t.

Details and Options
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Options  
DistanceFunction  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

FindHamiltonianPath

FindHamiltonianPath[g]

finds a Hamiltonian path in the graph g with the smallest total length.

FindHamiltonianPath[g,s,t]

finds a Hamiltonian path with the smallest total length from s to t.

Details and Options

  • FindHamiltonianPath is also known as the Hamiltonian path problem.
  • A Hamiltonian path visits each vertex exactly once.
  • FindHamiltonianPath returns the list {} if no Hamiltonian path exists.

Examples

open all close all

Basic Examples  (2)

Find a Hamiltonian path through vertices in a graph:

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

Highlight the path:

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

Find a Hamiltonian path between two individual vertices in a graph:

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"];
Wolfram Language code: FindHamiltonianPath[g, 1, 5]

Highlight the path:

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

Scope  (3)

FindHamiltonianPath works with undirected graphs:

Wolfram Language code: FindHamiltonianPath[[image]]

Weighted graphs:

Wolfram Language code: FindHamiltonianPath[[image]]

FindHamiltonianPath works with large graphs:

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

Options  (1)

DistanceFunction  (1)

This defines a sparse distance matrix among six points:

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: g = [image];

Find a Hamiltonian path:

Wolfram Language code: path = FindHamiltonianPath[g, DistanceFunction -> (d[[#1, #2]]&)]

Highlight the path:

Wolfram Language code: HighlightGraph[g, PathGraph[path]]

Applications  (2)

Find a sequence of moves by a knight chess piece that visits each square of an 8×8 chessboard exactly once:

Wolfram Language code: g = KnightTourGraph[8, 8];
Wolfram Language code: path = FindHamiltonianPath[g]

A knight's move:

Wolfram Language code: checkerboard = ArrayPlot[Table[Mod[j + i, 2], {i, 8}, {j, 8}], ColorRules -> {1 -> RGBColor[0, .55, .77], 0 -> RGBColor[.67, .9, .99]}, Frame -> False, DataRange -> {{1, 8}, {1, 8}}];
Wolfram Language code: Show[{checkerboard, HighlightGraph[g, PathGraph[path], GraphHighlightStyle -> "DehighlightHide", EdgeStyle -> Directive[Thick, Red]]}]

Find a Hamiltonian path of Europe from Greece to Germany:

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

Latitude and longitude of geographical centers:

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

Construct a weighted graph of Europe:

Wolfram Language code: adj = Table[QuantityMagnitude@GeoDistance[i, j], {i, pos}, {j, pos}] /. Quantity[0., _] -> Infinity;
Wolfram Language code: g = WeightedAdjacencyGraph[europe, adj];
Wolfram Language code: FindHamiltonianPath[g, Entity["Country", "Greece"], Entity["Country", "Germany"]]//Shallow

Show the tour:

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

Properties & Relations  (2)

A graph with a Hamiltonian path may not have a Hamiltonian cycle:

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

A graph with a Hamiltonian cycle has a Hamiltonian path:

Wolfram Language code: g = GraphData["Foster038A"]
Wolfram Language code: HamiltonianGraphQ[g]
Wolfram Language code: FindHamiltonianPath[g]
Wolfram Research (2015), FindHamiltonianPath, Wolfram Language function, https://reference.wolfram.com/language/ref/FindHamiltonianPath.html.

Text

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

CMS

Wolfram Language. 2015. "FindHamiltonianPath." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindHamiltonianPath.html.

APA

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

BibTeX

@misc{reference.wolfram_2026_findhamiltonianpath, author="Wolfram Research", title="{FindHamiltonianPath}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindHamiltonianPath.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

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