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

Ford-Fulkerson 方法

Ford-Fulkerson 方法

Ford-Fulkerson 方法把最大流问题化为“寻找增广路径并更新残量网络”的重复过程。本课将用整数容量网络实现完整算法,并说明它何时终止、为什么容量类型会影响可靠性。

学习目标

  • 理解增广路径、瓶颈容量和残量网络之间的关系。
  • 能够使用深度优先搜索实现 Ford-Fulkerson 方法。
  • 判断整数、有理数与无理数容量对终止性的影响。

核心原理

流网络由源点、汇点和带非负容量的有向边组成。合法流必须满足容量限制,并在除源点和汇点之外的每个顶点保持流量守恒。Ford-Fulkerson 不直接修改原容量,而是在残量网络中记录每条边还能增加多少流量。

每轮算法执行三个动作:

  1. 在残量容量大于 0 的边上寻找一条从源点到汇点的路径。
  2. 取路径上最小残量容量作为本轮瓶颈流量。
  3. 减少正向残量并增加反向残量,使后续轮次能够撤销或改道此前的选择。

Ford-Fulkerson 残量网络与增广路径

终止条件与容量限制

当残量网络中不存在源点到汇点的增广路径时,当前流就是最大流。若所有容量都是整数,每轮至少增加 1 个单位,因此算法会在有限轮内结束;使用邻接表寻找路径时,常写作 O(EF)O(EF),其中 FF 是最大流值,所以它是伪多项式复杂度。

有理数容量可以先按公分母缩放为整数。对于无理数容量,任意选择增广路径的版本可能无限执行,甚至不收敛到最大流。工程实现还要注意浮点误差,通常优先使用整数单位或定点数。

易错点

  • 忘记增加反向残量,会失去撤销错误路径选择的能力。
  • 直接覆盖原容量,导致无法区分输入数据与当前残量状态。
  • 把任意 DFS 路径选择误认为多项式时间保证;该保证属于后续的 Edmonds-Karp 算法。
  • 最大流可能超过 int 范围时,应把容量、瓶颈和累计流量统一改为 long。

完整可运行示例

下面的 Java 17 程序使用邻接矩阵保存容量,并用栈实现 DFS。网络包含源点 0、汇点 3,每次找到路径后立即更新残量矩阵。

java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class FordFulkersonDemo {

    public static void main(String[] args) {
        int[][] capacity = {
                {0, 3, 2, 0},
                {0, 0, 1, 2},
                {0, 0, 0, 3},
                {0, 0, 0, 0}
        };

        int maxFlow = fordFulkerson(capacity, 0, 3);
        System.out.println("最大流: " + maxFlow);
    }

    static int fordFulkerson(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;

        while (findAugmentingPath(residual, source, sink, parent)) {
            int bottleneck = Integer.MAX_VALUE;
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                bottleneck = Math.min(bottleneck, residual[u][v]);
            }

            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.println("本轮增广流量: " + bottleneck);
        }

        return maxFlow;
    }

    static boolean findAugmentingPath(
            int[][] residual, int source, int sink, int[] parent) {
        Arrays.fill(parent, -1);
        boolean[] visited = new boolean[residual.length];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(source);
        visited[source] = true;

        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v = 0; v < residual.length; v++) {
                if (!visited[v] && residual[u][v] > 0) {
                    parent[v] = u;
                    visited[v] = true;
                    stack.push(v);
                    if (v == sink) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
}

运行命令如下:

bash
javac FordFulkersonDemo.java
java FordFulkersonDemo

预期输出

text
本轮增广流量: 2
本轮增广流量: 2
本轮增广流量: 1
最大流: 5

三轮增广的总量为 2 + 2 + 1 = 5。当 DFS 再也找不到到达汇点的正残量路径时,循环结束。

练习

  1. 将边 2 -> 3 的容量从 3 改为 1,重新运行程序,并解释为什么最大流受汇点入边总容量限制。
  2. 在输出中加入每轮完整路径,验收条件是路径首点为 0、末点为 3,且打印的瓶颈等于该路径最小残量。

本课总结

  • Ford-Fulkerson 的本质是不断在残量网络中增广,并用反向边保留改道能力。
  • 整数容量保证有限终止,但运行时间依赖最大流数值,不是强多项式界。
  • 路径选择策略决定算法行为,任意 DFS 只是该方法的一种实现。

下一课预告

下一课将学习 Edmonds-Karp 算法,用 BFS 固定选择边数最少的增广路径,并推导它为什么具有 O(VE2)O(VE^2) 的多项式时间上界。

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

目录与阅读设置

阅读设置

17

记录一个想法

Ford-Fulkerson 方法

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

登录哪都通