# 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: