在上一篇我们提到了网络流算法Push-relabel，那是90年代提出的算法，算是比较新的，而现在要说的Dinic算法则是由以色列人Dinitz在冷战时期，即60-70年代提出的算法变种而来的，其算法复杂度为O(mn^2)。

Dinic算法主要思想也是基于FF算法的，改进的地方也是减少寻找增广路径的迭代次数。此处Dinitz大师引用了一个非常聪明的数据结构，Layer Network，分层网络，该结构是由BFS tree启发得到的，它跟BFS tree的区别在于，BFS tree只保存到每一层的一条边，这样就导致了利用BFS tree一次只能发现一条增广路径，而分层网络保存了到每一层的所有边，但层内的边不保存。

介绍完数据结构，开始讲算法的步骤了，1）从网络的剩余图中利用BFS宽度优先遍历技术生成分层网络。2）在分层网络中不断调用DFS生成增广路径，直到s不可到达t，这一步体现了Dinic算法贪心的特性。3）max_flow+=这次生成的所有增广路径的flow，重新生成剩余图，转1）。

源代码如下：

采用递归实现BFS和DFS，效率不高。

__author__ = 'xanxus'
nodeNum, edgeNum = 0, 0
arcs = []


class Arc(object):
    def __init__(self):
        self.src = http://www.mamicode.com/-1>

网络流算法Dinic的Python实现