Ford-Fulkerson算法

2025 年 3 月 17 日 | 阅读 1 分钟

最初，流的值为0。找到一些增广路径p，并增加路径p中每条边的流量f，增加值为残余容量c_f (p)。当不存在增广路径时，流量f是最大流量。

FORD-FULKERSON METHOD (G, s, t)
 1. Initialize flow f to 0
 2. while there exists an augmenting path p
 3. do argument flow f along p
 4. Return f

FORD-FULKERSON (G, s, t)
 1. for each edge (u, v) ∈ E [G]
 2. do f [u, v] ← 0
 3. f [u, v] ← 0
 4. while there exists a path p from s to t in the residual network G_f.
 5. do c_f (p)←min?{ C_f (u,v):(u,v)is on p}
 6. for each edge (u, v) in p
 7. do f [u, v] ← f [u, v] + c_f  (p)
 8. f [u, v] ←-f[u,v]

示例： 每条有向边都标有容量。使用Ford-Fulkerson算法找到最大流量。