数据结构与算法 / 系统课时

增广路径

增广路径

增广路径是在残量网络中从源点通向汇点的一条可行路径。算法找到它后,只需计算路径上的最小残量容量,就能安全增加总流量,并同步更新正向边与反向边,为下一轮搜索保留改路空间。

学习目标

  • 判断一条路径是否为合法增广路径。
  • 计算瓶颈容量并完成残量网络更新。
  • 使用 BFS 重复寻找增广路径并求得最大流。

从可行路径到流量增量

增广路径必须从源点开始、在汇点结束,并且路径上每条残量边的容量都大于 0。路径能够增加的流量由最小残量容量决定,这个最小值称为瓶颈容量。

例如,一条路径的残量容量依次为 8、3、6,则本轮最多增广 3 个单位。若强行增加 4 个单位,中间那条残量为 3 的边就会违反容量限制。

更新一条路径时,对路径上的每个方向 u -> v 执行两项操作:正向残量减去瓶颈容量,反向残量增加瓶颈容量。路径中即使包含反向残量边,也使用完全相同的更新形式;它在原网络中的效果就是撤销对应流量。

增广路径的寻找与残量更新流程

寻找与更新的执行顺序

  1. 在残量网络中只沿容量大于 0 的边进行搜索。
  2. 使用 parent 数组记录每个顶点的前驱,抵达汇点后反向还原路径。
  3. 扫描整条路径,取最小残量容量作为本轮瓶颈。
  4. 对每条路径边同步更新正向与反向残量容量。
  5. 累加总流量并重新搜索,直到源点无法到达汇点。

Ford-Fulkerson 方法允许使用 DFS、BFS 或其他方式寻找增广路径。固定使用 BFS 时得到 Edmonds-Karp 算法,其时间复杂度为 O(VE^2);BFS 会优先选择残量网络中边数最少的增广路径,使增广次数获得多项式上界。

完整可运行示例

下面的 Java 17 程序使用 BFS 寻找增广路径。每轮都会输出实际路径与瓶颈容量,最后给出最大流。程序假设源点与汇点不同,容量为非负整数。

java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

public class AugmentingPathDemo {

    private static final String[] NAMES = {"S", "A", "B", "C", "D", "T"};

    public static void main(String[] args) {
        int[][] capacity = new int[NAMES.length][NAMES.length];
        capacity[0][1] = 10;
        capacity[0][3] = 10;
        capacity[1][2] = 4;
        capacity[1][3] = 2;
        capacity[1][4] = 8;
        capacity[3][4] = 9;
        capacity[4][2] = 6;
        capacity[2][5] = 10;
        capacity[4][5] = 10;

        int maxFlow = edmondsKarp(capacity, 0, 5);
        System.out.println("最大流 = " + maxFlow);
    }

    static int edmondsKarp(int[][] capacity, int source, int sink) {
        int n = capacity.length;
        int[][] residual = new int[n][n];
        for (int i = 0; i < n; i++) {
            residual[i] = Arrays.copyOf(capacity[i], n);
        }

        int[] parent = new int[n];
        int maxFlow = 0;
        int round = 1;

        while (bfs(residual, source, sink, parent)) {
            int bottleneck = Integer.MAX_VALUE;
            List<Integer> path = new ArrayList<>();

            // 沿 parent 反向重建路径,并计算最小残量容量。
            for (int v = sink; v != source; v = parent[v]) {
                path.add(v);
                bottleneck = Math.min(bottleneck, residual[parent[v]][v]);
            }
            path.add(source);
            Collections.reverse(path);

            // 正向边减去流量,反向边增加可撤销流量。
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                residual[u][v] -= bottleneck;
                residual[v][u] += bottleneck;
            }

            maxFlow += bottleneck;
            System.out.printf("增广路径 %d: %s,瓶颈容量 = %d%n",
                    round++, formatPath(path), bottleneck);
        }

        return maxFlow;
    }

    static boolean bfs(int[][] residual, int source, int sink, int[] parent) {
        Arrays.fill(parent, -1);
        parent[source] = source;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(source);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v = 0; v < residual.length; v++) {
                if (parent[v] == -1 && residual[u][v] > 0) {
                    parent[v] = u;
                    if (v == sink) {
                        return true;
                    }
                    queue.offer(v);
                }
            }
        }
        return false;
    }

    static String formatPath(List<Integer> path) {
        List<String> names = new ArrayList<>();
        for (int vertex : path) {
            names.add(NAMES[vertex]);
        }
        return String.join(" -> ", names);
    }
}

运行命令:

bash
javac AugmentingPathDemo.java
java AugmentingPathDemo

预期输出:

text
增广路径 1: S -> A -> B -> T,瓶颈容量 = 4
增广路径 2: S -> A -> D -> T,瓶颈容量 = 6
增广路径 3: S -> C -> D -> T,瓶颈容量 = 4
增广路径 4: S -> C -> D -> B -> T,瓶颈容量 = 5
最大流 = 19

边界条件与常见错误

搜索条件必须检查 residual[u][v] > 0,而不是只看原始容量。原边即使存在,也可能已经饱和;原图中不存在的反向边,也可能因为已有流量而在残量网络中可用。

瓶颈容量必须在每轮重新初始化并扫描整条路径。更新时若忘记执行 residual[v][u] += bottleneck,程序可能在简单样例中得到正确结果,却无法撤销早期选择。容量总和可能超过 int 范围时,应把容量、残量和最大流统一改为 long。

当 BFS 无法从源点到达汇点时,当前流已经无法继续增广。根据最大流最小割定理,此时残量网络中源点可达集合与不可达集合之间的原边构成一个最小割。

本课练习

  1. 在示例中删除边 D -> T,手工预测每轮增广路径,再运行程序核对最大流。验收条件是路径输出与手算顺序一致,且每轮瓶颈不超过对应残量容量。
  2. 修改程序,使每轮增广后打印所有残量容量大于 0 的边。要求能够从输出中确认正向容量减少、反向容量增加,并解释至少一次反向边出现的原因。

本课总结

  • 增广路径只经过残量容量大于 0 的边,瓶颈容量决定本轮安全增量。
  • 每次更新都必须同时修改正向与反向残量,才能保留撤销和改路能力。
  • 使用 BFS 重复增广得到 Edmonds-Karp 算法,无增广路径时达到最大流。

下一课预告

下一阶段将把残量网络与增广路径组合成完整的最大流求解过程,并进一步理解最小割与二分图匹配之间的建模关系。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

增广路径

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通