第1个回答 2013-11-01
1.Fort_Fulkerson算法. 2.Edmonds_Karp算法. 3.Push_Relabel 算法 4.Relabel_to_Front算法.
<<算法艺术与信息学竞赛>>上介绍了五种算法.
1.Fort_Fulkerson算法. 2.最短增广路算法. 3.使用距离标号的最短增广路算法. 4.预流推进算法 5.最高标号的预流推进算法.
<<实用算法分析与程序设计>>上介绍了一种算法:
1.Dinic算法.
另外在网上又看见一些其它算法:
1.SAP算法. 2.pre_flow 算法 3.FIFO pre_flow算法 。。。 。。。
其实不少算法说的都是同一个东西，只是名称不一样，现在总结如下:
1.Fort_Fulkerson算法.
2.Edmonds_Karp算法(最短增广路算法).-------------------O( n*m^2 )
3.SAP算法(使用距离标号的最短增广路算法).--------------O( n^2*m )
4.Dinic算法.------------------------------------------------------O( n^2*m )
5.Push_Relabel算法(预流推进算法).------------------------O( n^2*m )
6.FIFO Preflow_Push算法.------------------------------------O( n^2*m)
7.Relabel_to_Front算法.---------------------------------------O( n^3 )
8.Highest Label Preflow_push算法.--------------------------O( n^2*m^1/2)