Chapter 15: 从路径说起

在图论中，通道（walk）、迹（trail）、路径（path）、回路（circuit）、环（cycle）这几个概念容易混淆。 它们的区别主要在于：是否允许重复节点、是否允许重复边、首尾是否闭合。

图论中存在多种经典路径问题，它们在节点要求、边要求、优化目标等方面各有不同。 理解这些问题的区别和联系，有助于选择合适的算法解决实际问题。

路径（path）是通道的一种特殊情况， 它确保每个节点和每条边只经过一次。 在完全图K₅中，任意两个节点之间存在多条路径， 其中长度最小的路径称为最短路径。 经过所有节点的路径称为哈密尔顿路径。

最短路径问题（Shortest Path Problem）是图论中的经典问题， 目标是在加权图中找到两个节点之间权重和最小的路径。 常用算法包括Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法等。 最短路径在导航系统、网络路由、物流配送等领域有广泛应用。

欧拉路径（Eulerian Path）是指通过图中每条边恰好一次的路径，起点和终点不同。欧拉回路（Eulerian Cycle）则是经过每条边恰好一次并回到起点的闭合路径。 如果图中存在欧拉回路，该图称为欧拉图。 欧拉路径问题源于著名的哥尼斯堡七桥问题，是图论的起源之一。

哈密尔顿路径（Hamiltonian Path）是指经过图中每个节点恰好一次的路径。哈密尔顿回路（Hamiltonian Cycle）是起点和终点相同的哈密尔顿路径。 与欧拉路径（经过所有边）不同，哈密尔顿路径关注节点。 判断一个图是否存在哈密尔顿路径是NP完全问题。 所有柏拉图图都存在哈密尔顿回路。

旅行商问题（Traveling Salesman Problem, TSP） 是哈密尔顿路径问题的加权版本。 目标是找到访问所有城市恰好一次并回到起点的最短回路。 TSP是NP困难问题，对于n个城市，可能的路线数为(n-1)!/2。 TSP在物流配送、芯片制造、基因测序等领域有重要应用。