关于网络流的普通残留网络增广和分层图增广的问题 - 数据结构与算法

编程论坛 → 开发语言 → 『数据结构与算法』 → 关于网络流的普通残留网络增广和分层图增广的问题

标题：关于网络流的普通残留网络增广和分层图增广的问题

只看楼主

朱涛

等　级：论坛游民
帖　子：6
专家分：15
注　册：2010-7-30

问题点数：0 回复次数：1

关于网络流的普通残留网络增广和分层图增广的问题

不太清楚普通残留网络（ford_fulkerson算法）和使用分层图网络（dinic）流进行增广有什么区别，分层图的优势在哪里？

搜索更多相关主题的帖子: 网络　增广　分层　

2010-08-02 12:27

朱涛

等　级：论坛游民
帖　子：6
专家分：15
注　册：2010-7-30

得分:0

自己回答自己把，dinic也是一种增广路算法，优势之处在于用广搜建立分层图之后可以对该图多次增广，通过一些搜索的策略设计可以使均摊时间复杂度达到O(n),而一直采用广度优先搜索来增广则每次增广时间复杂度都要达到O(m)，n为点的数量，m为边的数量。
所以优势就在于它的增广路寻找的更快

当做必做，坚持完成

2010-08-03 16:08