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 allclose all

Basic Examples  (1)

Find a Hamiltonian path through vertices in a graph:

Highlight the path:

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

Highlight the path:

Scope  (3)

FindHamiltonianPath works with undirected graphs:

Weighted graphs:

FindHamiltonianPath works with large graphs:

Options  (1)

DistanceFunction  (1)

This defines a sparse distance matrix among six points:

Find a Hamiltonian path:

Highlight the path:

Applications  (2)

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

A knight's move:

Find a Hamiltonian path of Europe from Greece to Germany:

Latitude and longitude of geographical centers:

Construct a weighted graph of Europe:

Show the tour:

Properties & Relations  (2)

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

A graph with a Hamiltonian cycle has a Hamiltonian path:

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_2025_findhamiltonianpath, author="Wolfram Research", title="{FindHamiltonianPath}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindHamiltonianPath.html}", note=[Accessed: 21-February-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_findhamiltonianpath, organization={Wolfram Research}, title={FindHamiltonianPath}, year={2015}, url={https://reference.wolfram.com/language/ref/FindHamiltonianPath.html}, note=[Accessed: 21-February-2025 ]}