基本概念

  Dinitz算法有时候也叫Dinic算法，它是在Ford-Fulkerson算法的基础上进行改良而来。使用了一个新概念，叫阻塞流blocking flow。
  阻塞流是在剩余网络里的流，是这样定义的，剩余网络里的所有的最短增广路径都含有一条饱和边，并且每条流量大于0的路径都在最短路径里。等于是找到所有的最短路径，然后让这些边大于0，并且最少有一条饱和边。
  等级图level graph，阻塞流需要找到所有的最短路径，为了找到所有的最短路径，需要用到等级图。等级图就是距离起点的距离图。利用等级图能快速寻找所有的最短路径。

算法过程

  外层循环和Ford-Fulkerson算法、Edmonds-Karp算法差不多，不过Ford-Fulkerson算法和Edmonds-Karp算法都是加上增广路径的最小剩余容量。而Dinitz算法是把整个阻塞流加进去。我还用那个图演示算法过程。
  最开始剩余网络就是原图：

  然后就是求阻塞流：

  把阻塞流加入到流中：

  再求新的剩余网络：

  根据新的剩余网络求出阻塞流：

  新的流：

  在这个图的剩余网络里再也找不到增广路径，跳出循环，求出了最大流。

Python实现

# _*_ coding:utf-8 _*_
class Edge:

    def __init__(self, to, weight):
        self.__to = to
        self.__weight = weight

    @property
    def to(self):
        return self.__to

    @to.setter
    def to(self, to):
        self.__to = to

    @property
    def weight(self):
        return self.__weight

    @weight.setter
    def weight(self, weight):
        self.__weight = weight


# 加权图
class FlowNetwork:

    def __init__(self, vertices, edges, s, t):
        self.__vertices = vertices
        self.__edges = edges
        self.__s = s
        self.__t = t

    def dinitz(self):

        # init

        flow = [[Edge(x.to, 0) for x in e] for e in self.__edges]
        pos = ["0,0!", "2,1!", "2,0!", "2,-1!", "4,1!", "4,0!", "4,-1!", "6,0!"]

        while (p := self.augmenting_path(flow)) is not None:
            # 找出最小的剩余容量
            # 首先创建剩余图
            residual_graph = self.residual_graph(flow)
            print("剩余网络", residual_graph.to_dot(pos))
            h = residual_graph.blocking_flow()
            print("阻塞流", residual_graph.to_flow_path_dot(pos, h[0], h[1]))
            path = p[0]

            # f上所有流量加上h流量
            for i in range(len(flow)):
                flows = flow[i]
                for x in flows:
                    f_h = FlowNetwork.get_flow(h[0], i, x.to)
                    if f_h is None:
                        f_h = 0
                    x.weight = x.weight + f_h
            print("流", self.to_flow_dot(pos, flow))
        return flow

    def blocking_flow(self):
        # BFS所有的最短路径
        h = [[Edge(x.to, 0) for x in e] for e in self.__edges]
        n = len(self.__vertices)
        levels = [n for _ in self.__vertices]
        levels[self.__s] = 0
        # 每个节点都是一个栈
        queue = [[self.__s]]
        all_path = []
        while len(queue) > 0:
            stack = queue.pop()
            node = stack[-1]
            if node == self.__t:
                # 栈里的最小剩余容量
                min_weight = None
                for i in range(len(stack) - 1):
                    p = stack[i]
                    c = stack[i + 1]
                    capacity = FlowNetwork.get_flow(self.__edges, p, c)
                    flow = FlowNetwork.get_flow(h, p, c)
                    residual_c = capacity - flow
                    min_weight = residual_c if min_weight is None else min(residual_c, min_weight)
                # 栈里全部加上最小剩余容量
                for i in range(len(stack) - 1):
                    p = stack[i]
                    c = stack[i + 1]
                    for x in h[p]:
                        if x.to == c:
                            x.weight += min_weight
                all_path.append(stack)
            else:
                for neighbour in self.__edges[node]:
                    # 不访问平级的，和上级的
                    n_index = neighbour.to
                    if levels[n_index] <= levels[node]:
                        continue
                    # 不能访问没有容量的：
                    c = FlowNetwork.get_flow(h, node, n_index)
                    if neighbour.weight - c > 0:
                        new_stack = stack[:]
                        new_stack.append(n_index)
                        queue.insert(0, new_stack)
                        levels[n_index] = levels[node] + 1

        return h, all_path

    def residual_graph(self, flow):
        # 首先点肯定是一样的
        # 边不一样而已
        edges = [None for e in self.__edges]
        for i, e in enumerate(self.__edges):
            # 点i的所有流量
            flows = flow[i]
            residual_edges = []
            for edge in e:
                f = FlowNetwork.get_flow(flow, i, edge.to)
                # 还有流量
                residual_capacity = edge.weight - f

                residual_edges.append(Edge(edge.to, residual_capacity))
            edges[i] = residual_edges
        return FlowNetwork(self.__vertices, edges, self.__s, self.__t)

    WHITE = 0
    GRAY = 1
    BLACK = 2

    def augmenting_path(self, flow):
        # 使用单源bfs找到路径
        parent_map = [None for _ in self.__vertices]
        # 因为python 没有hashset,所以以字典代替
        colors = [FlowNetwork.WHITE for _ in self.__vertices]
        colors[self.__s] = FlowNetwork.GRAY
        queue = [self.__s]
        e = self.__s

        while e != self.__t and len(queue) != 0:
            e = queue.pop(0)
            # 把点连接的点全部放入队列中
            for neighbor in self.__edges[e]:
                f = FlowNetwork.get_flow(flow, e, neighbor.to)
                cf = neighbor.weight - f
                if cf > 0:
                    if colors[neighbor.to] == FlowNetwork.WHITE:
                        # 必须是不饱和边
                        parent_map[neighbor.to] = e
                        queue.append(neighbor.to)
                        colors[neighbor.to] = FlowNetwork.GRAY
            colors[e] = FlowNetwork.BLACK
        # 没有找到
        if e != self.__t:
            return None

        # 找到之后组装路径
        path = [self.__t]
        end = self.__t
        min_cf = None
        while end != self.__s:
            # 不停地找parent
            c = FlowNetwork.get_flow(self.__edges, parent_map[end], end)
            f = FlowNetwork.get_flow(flow, parent_map[end], end)
            cf = c - f
            min_cf = cf if min_cf is None else min(min_cf, cf)
            end = parent_map[end]
            path.append(end)
        path.reverse()
        return path, min_cf

    @staticmethod
    def get_flow(flow, source, target):

        flows = flow[source]
        f = None
        for edge_flow in flows:
            if edge_flow.to == target:
                f = edge_flow.weight
        return f

    def to_dot(self, pos):
        dot_s = 'digraph s {\n\tlayout=fdp\n'
        for i, v in enumerate(self.__vertices):
            dot_s += f'\t"{v}"[pos="{pos[i]}"];\n'
        for i, e in enumerate(self.__edges):
            for t in e:
                dot_s += f'\t\"{self.__vertices[i]}\"->"{self.__vertices[t.to]}"[label="{t.weight}"];\n'
        dot_s += '}\n'
        return dot_s

    def to_flow_dot(self, pos, flow):
        dot_s = 'digraph s {\n\tlayout=fdp\nnode [shape = circle]\n'
        for i, v in enumerate(self.__vertices):
            dot_s += f'\t"{v}"[pos="{pos[i]}"];\n'
        for i, e in enumerate(self.__edges):
            for t in e:
                edge = f'\t\"{self.__vertices[i]}\"->"{self.__vertices[t.to]}"'
                dot_s += edge
                f = FlowNetwork.get_flow(flow, i, t.to)
                dot_s += f'[label="{f}/{t.weight}"];\n'
        dot_s += '}\n'
        return dot_s

    def to_flow_path_dot(self, pos, flow, paths):
        # 搞成邻接矩阵吧
        path_map = [[False for _ in self.__vertices] for _ in self.__vertices]
        for path in paths:
            for i in range(len(path) - 1):
                path_map[path[i]][path[i + 1]] = True
        dot_s = 'digraph s {\n\tlayout=fdp\nnode [shape = circle]\n'
        for i, v in enumerate(self.__vertices):
            dot_s += f'\t"{v}"[pos="{pos[i]}"];\n'
        for i, e in enumerate(self.__edges):
            for t in e:
                edge = f'\t\"{self.__vertices[i]}\"->"{self.__vertices[t.to]}"'
                dot_s += edge
                f = FlowNetwork.get_flow(flow, i, t.to)
                # 遇到路径就加粗
                dot_s += f'[label="{f}/{t.weight}";'
                if path_map[i][t.to]:
                    dot_s += 'color="red"'
                dot_s += '];\n'
        dot_s += '}\n'
        return dot_s

    @property
    def vertices(self):
        return self.__vertices

    @vertices.setter
    def vertices(self, value):
        self.__vertices = value

    @property
    def edges(self):
        return self.__edges

    @edges.setter
    def edges(self, value):
        self.__edges = value

    @property
    def s(self):
        return self.__s

    @s.setter
    def s(self, s):
        self.__s = s

    @property
    def t(self):
        return self.__t

    @t.setter
    def t(self, value):
        self.__t = value

Python测试代码

import unittest

from com.youngthing.graph.dinitz import Edge
from com.youngthing.graph.dinitz import FlowNetwork


class ForkFulkersonTestCase(unittest.TestCase):
    def test_dinitz(self):
        # 做一张图
        vertices = ['S', '2', '3', '4', '5', '6', '7', 'T']
        # 设计容量
        edges = [
            [Edge(1, 10), Edge(2, 5), Edge(3, 15)],
            [Edge(2, 4), Edge(4, 9), Edge(5, 15)],
            [Edge(3, 4), Edge(5, 8)],
            [Edge(6, 30)],
            [Edge(5, 15), Edge(7, 10)],
            [Edge(6, 15), Edge(7, 10)],
            [Edge(7, 10), Edge(2, 6)],
            []
        ]
        fn = FlowNetwork(vertices, edges, 0, 7)
        pos = ["0,0!", "2,1!", "2,0!", "2,-1!", "4,1!", "4,0!", "4,-1!", "6,0!"]
        print(fn.to_dot(pos))

        flow = fn.dinitz()
        print(fn.to_flow_dot(pos, flow))


if __name__ == '__main__':
    unittest.main()