对最大流算法中的 Edmonds-Karp 算法和 Dinic 算法设计原理背后的贪心思想的一些见解
一张流网络图 $G$ 中通常存在若干条从源点 $s$ 到汇点 $t$ 的增广路径 $p_i$。可以证明，在 Edmonds-Karp 算法的设计思想中，这些增广路径一定是按从短到长的顺序，‘贪心’地对最大流做出贡献的。换而言之，一个网络流逐步达到最大流的过程，相当于流先沿着最短的增广路径充满这条路径，接着再沿着下一条最短的路径流动，依次下去直到充满网络中的所有增广路径为止达到最大流，并且这个过程具有贪心选择性质。
但相对于一些容易理解的初级贪心算法而言，Edmonds-Karp 算法中贪心转移次数难以在事先确定。以一维前缀和算法为例，贪心方程的转移次数就是原数组的长度，这在题目中往往是一个确定的数值。而 Edmonds-Karp 算法中的路径之间是存在关联的，一条路径满流后，一些与该路径含公共边集的其他路径也有可能同时消失，也有一些因新增反向边而出现的新路径。这就导致了算法中的贪心转移次数难以事先给出一个确切的值，目前我们也只能通过证明得到该算法运行贪心转移次数的上界估计值为 $O(VE)$。
Dinic 算法实际上是对 Edmonds-Karp 算法设计原理的一种补充和扩展。在上面提到，一条增广路径满流后可能会导致一些原有的增广路径消失，并新增另一批增广路径。Dinic 算法每轮循环都会生成一张分层图，这相当于只考虑当前阶段的图中原有的增广路径，而不考虑因其中路径逐条增广而新增的反向边和新增的路径。由于该过程不考虑新增的反向边，这些因新反向边而新增的路径也就不会和原有的路径共用同一张分层图了；而在下一次生成分层图时，这些新增路径才会被记录在新的分层图中进行增广。如此反复，直到无法生成新的分层图为止时，网络流达到最大流。从而，我们证明了 Dinic 算法分层图迭代过程的正确性。
此外，类比 Edmonds-Karp 算法的路径长度递增性质的证明，我们也可以证明 Dinic 算法中因一次分层图迭代而新增的所有路径长度一定不小于分层图中原有的路径长度。
