Java教程

最大流问题——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算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!