迪尼茨算法

Dinic算法（又称Dinitz算法）是一个在网络流中计算最大流的强多项式复杂度的算法，设想由以色列（前苏联）的计算机科学家Yefim (Chaim) A. Dinitz在1970年提出。算法 ${\displaystyle }$的时间复杂度类似于Edmonds–Karp算法，其时间复杂度为 ${\displaystyle }$ ，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算法中，如果每次总选择最短的一条增广路，路径长度将单调增加，且算法总能终止。