以下簡單地整理網路上查到的 Hamiltonian path 與 Travelling Salesman Problem 介紹。

Hamiltonian path

What is Hamiltonian path?
Hamiltonian path is a path that visit every node only once. It can be an undirected or directed graph. Also it

Hamiltonian cycle
If a Hamiltonian path is a cycle then we call it A Hamiltonian cycle (or Hamiltonian circuit).

Hamiltonian path problem
Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete

Travelling Salesman Problem

What is Travelling Salesman Problem(TSP)?
There is a man traveling. He departures from a city and he wants to visit every cities(nods) with the shortest distance. In the end, he will go back to the origin city, and he can only stop in each city once.

Which means, TSP is looking for the shortest distance of Hamiltonian cycle.

reference:
演算法筆記
Wikipedia - TSP
Wikipedia - Hamiltonian path