Dinic算法

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也将算法与BFS和DFS结合起来，形成了当前版本的算法。[3]

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

设${\displaystyle G=((V,E),c,s,t)}$为一个每条边的容量为${\displaystyle c(u,v)}$，流为${\displaystyle f(u,v)}$的网络。

残留容量${\displaystyle c_{f}\colon V\times V\to R^{+}}$的定义为：

1. 如果${\displaystyle (u,v)\in E}$,

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

   ${\displaystyle c_{f}(v,u)=f(u,v)}$

2. 否则${\displaystyle c_{f}(u,v)=0}$。

则残留网络为${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$，其中

${\displaystyle E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}}$.

增广路指通过残留网络${\displaystyle G_{f}}$的从源点${\displaystyle s}$到汇点${\displaystyle t}$的一条有效路径。

定义${\displaystyle \operatorname {dist} (v)}$为${\displaystyle G_{f}}$中从源点${\displaystyle s}$到点${\displaystyle v}$的最短距离。那么${\displaystyle G_{f}}$的高度标号为${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$，其中

${\displaystyle E_{L}=\{(u,v)\in E_{f}:\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$.

设图${\displaystyle G'=(V,E_{L}',s,t)}$，其中${\displaystyle E_{L}'=\{(u,v):f(u,v)<c_{f}|_{E_{L}}(u,v)\}}$不包含从${\displaystyle s}$到${\displaystyle t}$的路径，则阻塞流为一条从${\displaystyle s}$到${\displaystyle t}$的流${\displaystyle f}$。

Dinic算法

输入:网络${\displaystyle G=((V,E),c,s,t)}$。

输出:${\displaystyle s-t}$的流${\displaystyle f}$的最大值。

1. 对每条边${\displaystyle e\in E}$，设${\displaystyle f(e)=0}$。
2. 在图${\displaystyle G}$的残留网络${\displaystyle G_{f}}$中计算${\displaystyle G_{L}}$。如果${\displaystyle \operatorname {dist} (t)=\infty }$停止程序并输出${\displaystyle f}$.
3. 在${\displaystyle G_{L}}$找到一条阻塞流${\displaystyle f\;'}$。
4. 将${\displaystyle \ f}$增加${\displaystyle f\;'}$并返回第二步。

可以证明每轮算法中找到的阻塞流的边数至少增加1，因此整个网络中最多有${\displaystyle n-1}$条阻塞流, ${\displaystyle n}$为网络中顶点的数量。高度标号${\displaystyle G_{L}}$可以在${\displaystyle O(E)}$的时间复杂度内用BFS构建，一条阻塞流可以在${\displaystyle O(VE)}$的复杂度内构建。因此，算法的时间复杂度为${\displaystyle O(V^{2}E)}$.

使用一种叫做动态树的数据结构，找到阻塞流的时间复杂度可以降到${\displaystyle O(E\log V)}$，此时Dinic算法的复杂度可以降到${\displaystyle O(VE\log V)}$.

• Tarjan, R. E. . 1983.

• 网络流
• Ford–Fulkerson算法