Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
有人可以指导我到一个网站,该网站提供了有关如何在图表上应用福特-富尔克森方法以找到最大流量的分步说明。
非常感谢你。
据我所知(链接)、维基百科(链接)和第一个替代的谷歌热门(链接)。
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
源代码示例:Java
同样有趣的是最小割定理。从源到汇的最大流量等于边的最小切割及其流量。我只是在学校里没解决这个问题:(
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm