个性化阅读
专注于IT技术分析

Ford-folkerson算法

最初, 值的流为0。找到一些扩充路径p, 并通过剩余容量cf(p)在p的每个边缘上增加流f。当不存在增加路径时, 流量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 Gf.
 5. do cf (p)←min?{ Cf (u, v):(u, v)is on p}
 6. for each edge (u, v) in p
 7. do f [u, v] ← f [u, v] + cf  (p)
 8. f [u, v] ←-f[u, v]

示例:每个定向边都标记有容量。使用Ford-Fulkerson算法查找最大流量。

Ford-folkerson算法

解:每个部分的左侧显示带有阴影阴影扩展路径p的残差网络Gf, 每个部分的右侧显示净流量f。

Ford-folkerson算法
Ford-folkerson算法
赞(0)
未经允许不得转载:srcmini » Ford-folkerson算法

评论 抢沙发

评论前必须登录!