前情提要Q我去看完了它就随便讲了讲这一节根本没仔细讲实现方法啊竟然A感觉是对的。这一节的 PPT 确实只给了结论和上界没有展开任何算法的伪代码。原因有两个都跟课程设计有关1. 这是算法课不是实现课PPT 的核心任务是给出问题定义、证明正确性、分析时间复杂度。具体的实现细节用 BFS 怎么找最短增广路径、优先队列怎么找最胖路径被留给了Java 代码文件FordFulkerson.java、FlowNetwork.java、FlowEdge.java教材第 6.4 节的完整代码和文字PPT 上只写结论最短路径用 BFS增广次数 ≤ ½EV最胖路径用优先队列增广次数 ≤ E ln(EU)。这些结论的来源是原论文Edmonds-Karp 1972、Dinitz 1970PPT 只是引用。2. 实现细节在代码文件里如果你去看FordFulkerson.java第 60-61 页已经给了部分代码你会发现hasAugmentingPath用的是BFS队列不是 DFS。edgeTo记录路径上的边。主循环调用hasAugmentingPath如果返回 true就计算瓶颈并增广。这就是“最短路径”策略的实现。PPT 没有单独讲“怎么用 BFS 找最短增广路径”因为它认为你已经在 BFS 那一章第 4.1 节学过 BFS 了这里只需要调用现成的 BFS 逻辑。3. 最胖路径和随机路径没有代码PPT 第 49 页的表格列了四种策略最短、最胖、随机、DFS但只有最短路径BFS在FordFulkerson.java里有实现。其他三种策略的代码没有出现在 PPT 或配套代码中因为最胖路径需要优先队列但优先队列的实现IndexMinPQ已经在最短路径那一章讲过了这里只需要把 BFS 换成优先队列。随机路径和 DFS 路径没有实际工程价值上界太差只是作为理论对比存在。4. 如果你需要实现细节你需要看的是教材第 6.4 节的文字部分或者直接读FordFulkerson.java的源码。PPT 的定位是“课堂讲义”不是“参考手册”。它的目标是把核心逻辑和复杂度分析讲清楚实现细节留给学生自己阅读代码。Q莫非增广其实很简单可是怎么判断再也无法增广了呢只有正向流没有反向流A增广本身不复杂在残量网络中找一条从 s 到 t 的有向路径沿路径增加瓶颈容量。复杂的是怎么找这条路径以及怎么保证增广次数不爆炸。怎么判断再也无法增广判断标准是在残量网络中从 s 出发做一次 BFS/DFS看能不能到达 t。如果 t 可达存在增广路径继续增广。如果 t 不可达没有增广路径算法终止。不是看“只有正向流没有反向流”。残量网络中可能同时存在正向边和反向边。终止的条件是从 s 出发沿着残量网络中所有残量容量 0 的有向边怎么走都走不到 t。终止时的残量网络长什么样当 t 从 s 不可达时残量网络被分成两个部分A从 s 可达的顶点集合。B其余顶点包括 t。此时所有从 A 到 B 的边正向残量容量 0即 flow capacity满的。所有从 B 到 A 的边反向残量容量 0即 flow 0空的。所以从 A 到 B 没有任何残量容量从 B 到 A 也没有任何残量容量。s 和 t 之间被彻底切断。反向边在终止时可能还存在吗可能存在。比如某条从 B 到 A 的边原方向是 B→A如果它有 flow 0那么它的反向边 A→B 就有残量容量。但 A→B 的方向是从 A 到 B如果这条边的残量容量 0那么 B 中的顶点就会从 s 可达矛盾。所以终止时所有从 A 到 B 的反向边残量容量必须为 0。这意味着从 B 到 A 的原边 flow 必须为 0。同理所有从 A 到 B 的正向边残量容量必须为 0即 flow capacity。增广为什么“简单”因为每次增广的物理动作很简单在残量网络中找一条 s→t 路径用 BFS 或 DFS。计算路径上所有边的最小残量容量瓶颈。沿路径更新流量正向边加瓶颈反向边减瓶颈。难点在于选择哪条路径。如果随便选增广次数可能爆炸第 40-48 页的坏情况。用 BFS 选最短路径边数最少可以保证增广次数 ≤ ½EV总时间 O(E²V)。这就是为什么 PPT 说“BFS 效果很好”。总结增广的动作本身简单。判断终止在残量网络中从 s 做 BFSt 不可达即终止。终止时残量网络被切成 A 和 B所有 A→B 正向边满所有 B→A 反向边空。复杂性在于选择增广路径的策略而不是增广动作本身。