算法笔记：求解最大流的高效算法 Dinic 算法

2018-3-30 13:00 |来自: 互联网 434 0

摘要: 之前介绍过求解最大流的一种方法：Ford - Fulkerson 算法，由于时间复杂度是 O ( n × m × m ) 的（n 为节点数，m 为边数），在边比较多时不够快速。今天讲讲另一个求解最大流的算法：Dinic 算法，相对来说会更高效 ...

之前介绍过求解最大流的一种方法：Ford - Fulkerson 算法，由于时间复杂度是 O ( n × m × m ) 的（n 为节点数，m 为边数），在边比较多时不够快速。今天讲讲另一个求解最大流的算法：Dinic 算法，相对来说会更高效一些，也不难理解。下面是一些相关的链接：