# FindHamiltonianPath

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

#### BibLaTeX

@online{reference.wolfram_2024_findhamiltonianpath, organization={Wolfram Research}, title={FindHamiltonianPath}, year={2015}, url={https://reference.wolfram.com/language/ref/FindHamiltonianPath.html}, note=[Accessed: 10-September-2024 ]}