网络流的最经典应用就是最大流....给定一个图...给出每条边能流过的最大流量...求源点到汇点的最大流量....
求解网络流的基本思想就是每次寻找增广路(就是源点到汇点的一条可行路)..然后ans+=增广路能流过的流量..更新剩余网络..然后再做增广路...直到做不出增广路..关于网络流入门最难理解的地方就是剩余网络了....为什么在找到一条增广路后...不仅要将每条边的可行流量减去增广路能流过的流量...还要将每条边的反向弧加上增广路能流过的流量.?..原因是在做增广路时可能会阻塞后面的增广路...或者说做增广路本来是有个顺序才能找完最大流的.....但我们是任意找的...为了修正...就每次将流量加在了反向弧上...让后面的流能够进行自我调整...剩余网络的更新(就在原图上更新就可以了):
求解最大流流最原始的算法是Ford_Fulkerson..也就是上面提到的每次找任意的找增广路...加上增广路流量再更新剩余网络...可以看出找最大流最耗时的地方就是寻找增广路..Edmonds_Karp是对Ford_Fulkerson的一个优化算法...Ford_Fulkerson是任意寻找增广路...而Edmonds_Karp是每次寻找从源点到汇点可行的最短的增广路...其优势是可以在前期就卡断很多不必要的寻找增广路而又到不了汇点的过程...其优化的方法也很简单..就是将Ford_Fulkerson找增广路的过程用BFS实现..
一个找最大流更好的优化则是Dinic..优化的地方也是找增广路的过程....Dinic做了一个预处理...将所有点按到源点的距离分层...然后在寻找增广路时..只有要拓展点与当前点的距离差为1时才拓展...其原理我还没弄明白..只知道算法的基本思路...
Dinic的过程是 :
1、BFS做出层次网络
2、DFS寻找增广路
Dinic在寻找增广路用DFS上还有一点....就是找到一条增广路并将流量流过去后...就弹栈到这条增广路上流量最小的边(也就是这条增广路流过了流量之后...可行流量为0的边..)的前面的点再继续DFS....
听说SAP的效率比Dinic更高...但是有一些小Trick要留意...很容易被卡....所以暂时没有想着去了解SAP了..求解最大流的还有一种完全不同的思路就是预推流...啥时候再研究一下吧..
分享到:
相关推荐
使用Edmonds_Karp 算法解决最大流问题,网络流
匈牙利算法(Hungarian method)是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是二分图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求...
EK算法的C++实现,用于求有向图的最大流。
用于计算最大网络流的经典的Edmonds-Karp算法,代码自带例子,边权支持double类型。
资源来自pypi官网。 资源全名:ufal.chu_liu_edmonds-1.0.1-cp35-cp35m-win_amd64.whl
Implementation of Edmonds Karp algorithm that calculates maxFlow of graph. Input: For each test case, the first line contains the number of vertices (n) and the number of arcs (m). Then, there exist m...
python库,解压后可用。 资源全名:ufal.chu_liu_edmonds-1.0.1-cp35-cp35m-win_amd64.whl
最大流的算法——Edmonds-Karp算法(最短路径增广算法) 这里介绍一个最简单的算法:Edmonds-Karp算法 即最短路径增广算法 简称EK算法 EK算法基于一个基本的方法:Ford-Fulkerson方法 即增广路方法 简称FF方法 增广...
edmonds-karp启发式最大流算法
最大流中经典的算法。是对福特福克森算法的改进。在选择剩余网络的可增道路时选择s到t的最短道路。代码我写了详细的步骤汉字解释,方便理解。并以算法导论第二版例子为例,计算结果,和书中结果相符。
edmonds和dinic算法c++比较, 可以手动输入节点数和边数
1.6.3.1. 最大流 Maximum flow 1.6.3.1.1. 基本算法 Basic algorithms 1.6.3.1.1.1. Ford-Fulkerson method 1.6.3.1.1.1.1. Edmonds-Karp algorithm 1.6.3.1.1.1.1.1. Minimum length path 1.6.3.1.1.1.1.2. Maximum...
Edmonds-karp算法的Python实现版,可用于解决最大流问题,
最大流 Maximum flow 1.6.3.1.1. 基本算法 Basic algorithms 1.6.3.1.1.1. Ford-Fulkerson method 1.6.3.1.1.1.1. Edmonds-Karp algorithm 1.6.3.1.1.1.1.1. Minimum length path 1.6.3.1.1.1.1.2. Maximum ...
埃德蒙兹卡普Edmonds-Karp最大流算法的C ++实现。
网络流之费用流,讲述了Edmonds-Karp增广路算法 与其正确性证明,时间复杂度,还有几道例题与讲解。
网络流算法的详细介绍,包括Ford-Fulkerson 算法、Edmonds-Karp 算法、Dinic 算法。有详细图例,很容易理解
网络流算法模版--C++写的 Edmonds-Karp算法
网络流的基础概念,定理,和一些基本算法(Edmonds-Karp,Dinic,ISAP,Primal-Dual 原始对偶算法(费用流))的详细解释。还有一些经典例题的题解。
1.代码实现Preflow Push最大流算法 2.代码实现Edmonds最大流算法 3.讨论两个算法的运行性能