最大流问题——Ford-Fulkerson算法

本文主要是介绍最大流问题——Ford-Fulkerson算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

该算法的核心是三个重要的概念：

1.残存网络（residual network) : 指的是除去一条路径并对该路径加上取反边之后的网络，实际上表示可供反悔的网络

2.增广路径 (augmenting path) ：指的是残存网络中可以从s到t连通的一条路径

3.割(cut)：指的是截面的切割

切割的容量：指的是一个切割的正向边的容量和

切割的净流量：指的是一个切割的正向边流量减去负向边流量。

最大流最小切割定理：最大流量等于最小切割容量

另外的概念：

1.残存容量：在一条增广路径p上能够为每条边增加的流量的最大值。

Ford-Fulkerson算法：

1.先把所有边的flow置为零

2.（可以用广搜）找到一条路径，建立残存网络。

3.找到这条路径中边的最小残存容量

4.这个路径的每条非残存边的流加上这个容量。否则在其反向边减去此流量。

5.继续遍历新的路径直到此残存网络不再存在一条通路

这篇关于最大流问题——Ford-Fulkerson算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程