基于连续最短增广链的网络最大流分析

Network Maximum Flow Analysis Base on Dinic’s Algorithm

本文主要是分析连续最短增广链算法计算网络最大流的问题。先综述残留网络和层次网络的基本概念,然后分析连续最短增广链算法计算网络最大流的具体过程,再通过与Ford-Fulkerson (福特-富尔克森算法)和Edmonds-Karp (埃德蒙兹-卡普算法)算法进行比较来体现出连续最短增广链算法的突出点。通过相关性的比较,结论是连续最短增广链算法运行效果明显比Ford-Fulkerson好,且优于Edmonds-Karp。

This paper mainly analyzes the problem of calculating the maximum flow of the network by the Dinic algorithm. First we review the basic concepts of residual networks and hierarchical networks, then analyze the specific process of calculating the maximum flow of the network by the Dinic algorithm. By comparing with the Ford-Fulkerson algorithm and the Edmonds-Karp algorithm, the highlight of the Dinic algorithm is demonstrated. Through the comparison of correlations, the con-clusion is that the Dinic algorithm works better than Ford-Fulkerson and is better than Edmonds-Karp.