1. 概述
在本教程中，我们将讨论如何在图中找到一条遍历所有节点的最短路径。
我们将首先明确问题定义并给出一个示例。随后，介绍两种不同的解决方案：暴力法和基于 Dijkstra 的状态压缩法。
2. 问题定义
给定一个图 $ G $，其中包含 $ V $ 个节点（编号从 $ 0 $ 到 $ V - 1 $）和 $ E $ 条带权边。我们的任务是找出一条路径，遍历所有节点，并使该路径的总权重最小。
需要注意的是：
- 我们可以重复访问节点
- 路径的起点和终点可以是任意节点
- 所求路径是所有满足“遍历所有节点”条件的路径中总权重最小的那一个
来看一个示例：
上图中，遍历所有节点的最短路径为：0 → 1 → 4 → 1 → 2 → 3，总权重为 6。
3. 暴力法
3.1. 核心思想
- 枚举所有节点的排列顺序
- 每个排列表示一个访问顺序
- 使用 Floyd-Warshall 算法预处理任意两点间的最短路径
- 对每个排列，计算路径总权重，取最小值作为答案
3.2. 实现代码
algorithm BruteForceApproach(V, G):
// INPUT
// V = the number of nodes in the graph
// G = the graph stored as an adjacency list
// OUTPUT
// Returns the shortest path visiting all nodes in G
answer <- infinity
distance <- Calculate_Floyd_Warshall(G) // a matrix
permutations <- Calculate_Permutations()
for permutation in permutations:
cost <- 0
previous <- permutation[0]
for node in permutation:
cost <- cost + distance[previous, node]
previous <- node
if cost < answer:
answer <- cost
return answer
3.3. 时间复杂度分析
- Floyd-Warshall：$ O(V^3) $
- 所有排列数量为 $ V! $，每个排列遍历需要 $ O(V) $
- 总时间复杂度：**$ O(V^3 + V \times V!) $**
⚠️ 该方法仅适用于 $ V \leq 10 $ 的小规模图，否则计算量爆炸
4. Dijkstra 状态压缩法
4.1. 核心思想
使用 Dijkstra 算法的变种，结合状态压缩（bitmask）来表示已访问的节点集合：
- 每个状态用
(当前节点, 已访问节点集合)表示 - 初始时，每个节点作为起点，其 bitmask 只有对应位为 1
- 使用优先队列进行松弛操作，逐步更新状态
- 最终答案为所有节点中，bitmask 全为 1 时的最小代价
✅ 优点：相比暴力法，大大减少了无效路径的计算
❌ 缺点：空间复杂度较高，适用于 $ V \leq 16 $ 的情况
4.2. 实现代码
algorithm DijkstraApproach(V, G):
// INPUT
// V = the number of nodes in the graph
// G = the graph stored as an adjacency list
// OUTPUT
// Returns the shortest path visiting all nodes
cost <- a matrix whose all entries are infinity
priority_queue <- make an empty priority queue
for node from 0 to V-1:
priority_queue.add(node, 2^node)
cost[node, 2^node] <- 0
while priority_queue is not empty:
current <- priority_queue.front().node
mask <- priority_queue.front().bitmask
priority_queue.pop()
for child in G[current]:
add <- weight(current, child)
if cost[child, mask or 2^child] > cost[current, mask] + add:
priority_queue.add(child, mask or 2^child)
cost[child][mask or 2^child] <- cost[current][mask] + add
answer <- infinity
for node from 0 to V-1:
answer <- min(answer, cost[node, 2^V - 1])
return answer
4.3. 时间复杂度分析
- 状态总数为 $ V \times 2^V $
- 每次状态入队出队操作为 $ O(\log(V \times 2^V)) $
- 总时间复杂度：**$ O(V \times 2^V \times \log(V \times 2^V)) $**
5. 总结
我们讨论了图中遍历所有节点的最短路径问题，并提供了两种解决方案：
| 方法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 暴力法 | $ O(V^3 + V \times V!) $ | $ V \leq 10 $ |
| Dijkstra + Bitmask | $ O(V \times 2^V \times \log(V \times 2^V)) $ | $ V \leq 16 $ |
✅ 推荐使用第二种方法，尤其在节点数稍多时优势明显
⚠️ 注意空间开销，合理设置状态数组大小