Dinic算法

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

历史

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，因此整个网络中最多有条阻塞流, 为网络中顶点的数量。高度标号可以在的时间复杂度内用BFS构建，一条阻塞流可以在的复杂度内构建。因此，算法的时间复杂度为.
使用一种叫做动态树的数据结构，找到阻塞流的时间复杂度可以降到，此时Dinic算法的复杂度可以降到.

特殊情况

在具有单位容量的网络中，Dinic算法可以在更短的时间内输出结果。每条阻塞流可以在的时间内构建，并且阶段（phases）的数量不超过或。此时算法的复杂度为。
在二分图匹配问题的网络中，阶段的数量不超过，算法的时间复杂度不超过。这种算法又被叫做Hopcroft-Karp算法。更普遍的情况是，这种复杂度对unit网络 — 网络中的顶点要么与源点相连，要么与汇点相连，要么是一个顶点的单一外向边，并且所有的容量限制都是整数。