版权归原作者所有,如有侵权,请联系我们

[科普中国]-Dinic算法

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏

**Dinic算法(又称Dinitz算法)**是一个在网络流中计算最大流的强多项式复杂度的算法,设想由以色列(前苏联)的计算机科学家Yefim (Chaim) A. Dinitz在1970年提出。

历史Yefim Dinitz在Adel'son-Vel'sky(AVL树的发明者之一)的算法课的课前活动上发明了这个算法。当时他不知道关于Ford–Fulkerson算法的基本事实。

Dinitz在1969年一月向他人公布了他发明的算法,又在1970年将其发布在Doklady Akademii nauk SSSR杂志上。 在1974年,Shimon Even和(他之后的博士学生)Alon Itai在海法的以色列理工学院对Dinitz的算法以及Alexander Karzanov的阻塞流的想法很感兴趣。但是杂志上的文章每篇的篇幅被限制在四页以内,很多细节都被忽略,这导致他们很难根据文章还原出算法。但他们没有放弃,在后三天不断地努力,设法了解这两个文件中的分层网络的维护问题。 在接下来的几年,Even由于在讲学中将Dinitz念为Dinic,导致Dinic算法反而成为了它的名称。 Even和Itai也将算法与BFS和DFS结合起来,形成了当前版本的算法。

在Ford–Fulkerson算法被发明之后的约十年之内,使算法能在多项式复杂度之内处理不合理的边界的方法是未知的。这造成缺乏任何已知的多项式复杂度算法解决最大流问题。 Dinitz算法和Edmonds–Karp算法在1972年发布,证明在Ford–Fulkerson算法中,如果每次总选择最短的一条增广路,路径长度将单调增加,且算法总能终止。1

算法介绍层次图层次图,就是把原图中的点按照点到源的距离分“层”,只保留不同层之间的边的图。1

算法流程1、根据残量网络计算层次图。

2、在层次图中使用DFS进行增广直到不存在增广路。

3、重复以上步骤直到无法增广。

时间复杂度因为在Dinic的执行过程中,每次重新分层,汇点所在的层次是严格递增的,而n个点的层次图最多有n层,所以最多重新分层n次。在同一个层次图中,因为每条增广路都有一个瓶颈,而两次增广的瓶颈不可能相同,所以增广路最多m条。搜索每一条增广路时,前进和回溯都最多n次,所以这两者造成的时间复杂度是O(nm);而沿着同一条边(i,j)不可能枚举两次,因为第一次枚举时要么这条边的容量已经用尽,要么点j到汇不存在通路从而可将其从这一层次图中删除。综上所述,Dinic算法时间复杂度的理论上界是O(n^2*m)。

代码实现递归实现

代码简短,效率略低。(不是dinic,是最短路径增值)

boolbuild()//建立层次图{intx,y;memset(d,-1,sizeof(d));memset(G,-1,sizeof(G));bg=ed=d[s]=0;Q[ed++]=s;G[s]=g[s];while(bg