1. 概述
在本教程中，我们将探讨图论中的“最大-最小容量路径”（Maximum-Minimum Path Capacity）问题。我们会定义这个问题的含义、解决方法，并与 Dijkstra 算法进行对比。
2. 问题定义
最大-最小容量路径问题适用于带权图。
我们把每条边的权重视为该边的 容量。任务是找出从源节点 S 到目标节点 G 的所有路径中，具有最大容量的路径。而一条路径的容量，由这条路径中容量最小的那条边决定。
举个实际例子：假设图中的边表示管道的每秒最大输水能力，那么我们希望找到一条路径，使得整条路径的输水能力尽可能大。但整条路径的输水能力受限于路径中最细的那个管道。
3. 示例
以下是一个示例图，源节点为 S，目标节点为 G：
从图中可以看出，从 S 到 G 有多种路径，每条路径的容量如下表所示：
| 路径 | 边容量列表 | 最小容量 |
|---|---|---|
| SADG | 2, 9, 7 | 2 |
| SADEG | 2, 9, 5, 3 | 2 |
| SBEDG | 7, 4, 5, 7 | 4 |
| SBEG | 7, 4, 3 | 3 |
| SCEG | 8, 1, 3 | 1 |
✅ 在所有路径中，路径 SBEDG 的最小容量最大，为 4。
因此，这张图的最大-最小容量路径值为 4。
4. 算法实现
为了解决这个问题，我们可以使用一种基于 Dijkstra 算法的变种。
4.1. 与 Dijkstra 算法的区别
- 使用一个
capacity[]数组代替distance[]，记录每个节点从源点出发的最大最小容量。 - 初始化时，源点的容量为
+∞，其余节点初始化为-∞。 - 每次选择当前容量最大的节点进行处理，而不是最小的。
- 更新相邻节点容量的方式不同：新容量是当前节点容量与边容量的较小值。
✅ 算法正确性证明：
我们总是优先处理当前容量最大的节点，因此当目标节点被取出时，后续节点的容量一定更小。这就保证了找到的路径是最大最小容量路径。
4.2. 伪代码实现
algorithm findMaxMin(G, source, prev):
// G: 图结构
// source: 起始节点
// prev: 前驱节点数组
// 返回每个节点从 source 出发的最大最小容量
capacity <- -infinity
prev <- undefined
capacity[source] <- infinity
Q <- 所有节点集合
while Q 不为空:
u <- Q 中 capacity 最大的节点
if capacity[u] = -infinity:
break
for v in u 的邻居:
newCapacity <- min(capacity[u], u-v 边的容量)
if newCapacity > capacity[v]:
capacity[v] <- newCapacity
prev[v] <- u
Q.update(v)
return capacity
💡 实现细节：
- 可以使用一个有序集合（如 Java 中的
TreeSet）来维护节点，按 capacity 降序排序。 - 每次取出 capacity 最大的节点处理。
- 时间复杂度为 **O(E log V)**，与 Dijkstra 算法相近。
4.3. 路径还原
我们可以通过 prev[] 数组还原出最大最小容量路径：
algorithm FindMaxMinPath(G, source, goal):
findMaxMin(G, source, prev)
u <- goal
path <- 空列表
while u 不为 null:
path.add(u)
u <- prev[u]
reverse(path)
return path
✅ 复杂度分析：
- 不包括
findMaxMin()的部分，路径还原的时间复杂度为 **O(V)**。
5. 总结
本教程介绍了图中最大-最小容量路径问题的定义和解决方法：
- 该问题关注路径中最小边的容量，目标是找到整体容量最大的路径；
- 算法基于 Dijkstra 改进，主要区别在于：
- 使用 capacity 数组代替 distance；
- 每次选择 capacity 最大的节点；
- 更新逻辑为取当前 capacity 和边容量的最小值；
- 可以使用
prev[]数组还原路径； - 时间复杂度为 **O(E log V)**，适合中等规模图结构。
这个算法在现实场景中非常实用，比如网络带宽优化、管道输送系统设计等。