编程论坛
注册
登录
编程论坛
→
数据结构与算法
关于网络流的普通残留网络增广和分层图增广的问题
朱涛
发布于 2010-08-02 12:27, 1162 次点击
不太清楚普通残留网络(ford_fulkerson算法)和使用分层图网络(dinic)流进行增广有什么区别,分层图的优势在哪里?
1 回复
#2
朱涛
2010-08-03 16:08
自己回答自己把,dinic也是一种增广路算法,优势之处在于用广搜建立分层图之后可以对该图多次增广,通过一些搜索的策略设计可以使均摊时间复杂度达到O(n),而一直采用广度优先搜索来增广则每次增广时间复杂度都要达到O(m),n为点的数量,m为边的数量。
所以优势就在于它的增广路寻找的更快
1