3

有人可以指导我到一个网站，该网站提供了有关如何在图表上应用福特-富尔克森方法以找到最大流量的分步说明。

非常感谢你。

4

3 回答 3

3

据我所知（链接）、维基百科（链接）和第一个替代的谷歌热门（链接）。

Ford-Fulkerson 标记算法

  • （初始化）设 x 是一个初始可行流（例如，对于 E 中的所有 e，x(e) = 0）。
  • （流增广）如果残差网络上没有从 s 到 t 的增广路径，则停止。当前的 x 是最大流量。如果存在流增广路径 p，则将流 x 替换为 2。
    • x(e)=x(e)+delta 如果 e 是 p 上的前弧。
    • x(e)=x(e)-delta 如果 e 是 p 上的后向弧。其中 delta 是 p 上剩余容量的最小值。重复此步骤。

源代码示例：Java

于 2010-11-03T23:40:53.577 回答
0

同样有趣的是最小割定理。从源到汇的最大流量等于边的最小切割及其流量。我只是在学校里没解决这个问题:(

http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

于 2013-03-06T00:56:34.680 回答
0

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

于 2010-11-03T20:36:50.133 回答