打开主菜单

Dinic算法(又称Dinitz算法)是一个在网络流中计算最大流强多项式复杂度的算法,设想由以色列前苏联)的计算机科学家Yefim (Chaim) A. Dinitz在1970年提出。[1] 算法 的时间复杂度类似于Edmonds–Karp算法,其时间复杂度为 ,Dinic算法与Edmonds–Karp算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。Dinic算法中采用高度标号(level graph)以及阻塞流(blocking flow)实现其性能。

目录

历史编辑

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

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

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

定义编辑

 为一个每条边的容量为 ,流为 的网络。

残留容量 的定义为:
  1. 如果 ,
     
     
  2. 否则 
残留网络 ,其中
 .
增广路指通过残留网络 的从源点 到汇点 的一条有效路径。
定义  中从源点 到点 的最短距离。那么 高度标号 ,其中
 .
设图 ,其中 不包含从  的路径,则阻塞流为一条从  的流 

算法编辑

Dinic算法

输入:网络 
输出: 的流 的最大值。
  1. 对每条边 ,设 
  2. 在图 的残留网络 中计算 。如果 停止程序并输出 .
  3.  找到一条阻塞流 
  4.  增加 并返回第二步。

分析编辑

可以证明每轮算法中找到的阻塞流的边数至少增加1,因此整个网络中最多有 条阻塞流,  为网络中顶点的数量。高度标号 可以在 的时间复杂度内用BFS构建,一条阻塞流可以在 的复杂度内构建。因此,算法的时间复杂度为 .

使用一种叫做动态树的数据结构,找到阻塞流的时间复杂度可以降到 ,此时Dinic算法的复杂度可以降到 .

特殊情况编辑

在具有单位容量的网络中,Dinic算法可以在更短的时间内输出结果。每条阻塞流可以在 的时间内构建,并且阶段(phases)的数量不超过  。此时算法的复杂度为 [4]

二分图匹配问题的网络中,阶段的数量不超过 ,算法的时间复杂度不超过 。这种算法又被叫做Hopcroft-Karp算法。更普遍的情况是,这种复杂度对unit网络 — 网络中的顶点要么与源点相连,要么与汇点相连,要么是一个顶点的单一外向边,并且所有的容量限制都是整数。[5]

参考文献编辑

  1. ^ Yefim Dinitz. Algorithm for solution of a problem of maximum flow in a network with power estimation (PDF). Doklady Akademii nauk SSSR. 1970, 11: 1277–1280. 
  2. ^ Ilan Kadar; Sivan Albagli. Dinitz's algorithm for finding a maximum flow in a network. 2009-11-27. 
  3. ^ Yefim Dinitz. Dinitz's Algorithm: The Original Version and Even's Version (PDF). 
  4. ^ Even, Shimon; Tarjan, R. Endre. Network Flow and Testing Graph Connectivity. SIAM Journal on Computing. 1975, 4 (4): 507–518. ISSN 0097-5397. doi:10.1137/0204043. 
  5. ^ Tarjan 1983, p. 102.

参见编辑