概念

  预流preflow,是一种允许溢出的流，也就是中间节点不需要满足守恒律conservation的流，说得更清楚一点就是流入的流量大于流出的流量。下图是一个预流（图片来自上海交通大学）：

  溢出excess，在预流中，由于中间节点不满足流量守恒，进入的减去流出的，就称为溢出。上图中u点的溢出就是1。
  有效距离标签valid distance labeling，符号为$d(i)$,也叫高度函数Height Function,符号为h(i)。高度函数定义是终点高度为0，起点高度函数为点的个数。对于中间节点，需要满足以下要求，当存在从点i到点j的剩余容量边的时候，$d(i)\le d(j)+1$。其实高度函数是BFS计算距离用的。
  在预流下，如果存在有效距离标签，那么剩余网络里没有增广路径，此时，达到最大流。证明我就不去证明了。
  逆流，这是我自己发明的词哈，在Push-relabel算法中，为了辅助运算，需要在剩余网络中虚拟一个逆流，也就是反向的流，反向流可以超出容量限制。这种反向流是为了方便寻找邻居，是push-relabel算法特有的。

算法过程

  算法的核心思想是渐渐地将预流转变为流，此时的流就是最大流。把预流转变为流的方法就是将溢出不断地把流推到目标点sink去。如果sink装不下，就从逆流推回源头source。
  在循环的过程中，不断地在非终点的节点中找溢出点。找到溢出点后，如果溢出点周围没有可以流向的点，就提升溢出点的高度，如果有，那么就流向高度低的点。高度低的如果是正常的流，就增加流量，如果是逆流，就减少流量。
  如果没找到溢出点，那就发现了最大流了。
  算法过程我举个例子，先把源头灌满，并虚拟一个反向的流，反向流我用红色标注,图中的三个数字，第一个是节点名称，第二个是高度，第三个是溢出值：

  溢出点是A，此时邻居高度都是比自己高或平级，那就增加高度：

  增加高度后，再流向低点B：

  然后A还是溢出，那么就通过减少逆流，输回S：

  这时候B还是溢出，但是B高度不够，于是提升高度：

  高度够了，输往T：

  此时，最大流已经找到。

Python实现：

# _*_ coding:utf-8 _*_
# 加权图
class FlowNetwork:

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

    def push_relabel(self):
        # 这次用邻接矩阵，这样比较好写代码
        # 流
        f = [[0 for _ in self.__vertices] for _ in self.__vertices]
        # 初始化为溢出流
        s = self.__s
        for j, c_s_j in enumerate(self.__edges[s]):
            f[s][j] = c_s_j
            # 反向的暗流
            f[j][s] = c_s_j

        # 距离函数
        d = [0 for _ in self.__vertices]
        n = len(self.__vertices)
        d[s] = n
        # 如果存在溢出
        count = 0
        while (excess_tuple := self.excess(n, f)) is not None:
            i = excess_tuple[0]
            print(f"溢出点{self.__vertices[i]}，溢出{excess_tuple[1]},{count}次循环", self.to_flow_height_dot(f, d))
            # for i in range(n - 1):
            # print(self.to_flow_height_dot(f, d))
            # 检查可以push?
            can_push = False
            excess_i = excess_tuple[1]
            for j, c_i_j in enumerate(self.__edges[i]):
                if j == i:
                    continue
                if d[i] != d[j] + 1:
                    continue
                if c_i_j > 0:
                    residual_i_j = c_i_j - f[i][j]
                    if residual_i_j > 0:
                        delta = min(excess_i, residual_i_j)
                        f[i][j] = f[i][j] + delta
                        # 反向的暗流减少
                        f[j][i] = f[j][i] + delta
                        excess_i -= delta
                        can_push = True
                # 反向的
                elif f[i][j] > 0:
                    delta = min(excess_i, f[i][j])
                    f[i][j] = f[i][j] - delta
                    f[j][i] = f[j][i] - delta
                    excess_i -= delta
                    can_push = True

            if not can_push:
                # relabel
                min_d = self.min_d(d, f, i)

                print(f"relabel{self.__vertices[i]} = {d[i]}")
                d[i] = min_d + 1
            count += 1
            if count > 200:
                break
        return f

    def min_d(self, d, flow, i):
        min_distance = None
        # 正向计算剩余流量
        for j, c in enumerate(self.__edges[i]):
            if c > 0:
                residual_capacity = c - flow[i][j]
                if residual_capacity > 0:
                    min_distance = d[j] if min_distance is None else min(min_distance, d[j])
        # 计算回流
        for j, line in enumerate(self.__edges):
            c = line[i]
            if c > 0:
                residual_capacity = flow[j][i]
                if residual_capacity > 0:
                    min_distance = d[j] if min_distance is None else min(min_distance, d[j])
        return min_distance

    def excess(self, n, f):
        for i in range(n):
            if i == self.__t:
                continue
            excess_i = self.get_excess(f, i)
            if excess_i > 0:
                return i, excess_i
        return None

    def get_excess(self, f, i):
        in_i = 0
        for j, line in enumerate(f):
            # 不能计算反向暗流
            if self.__edges[j][i] > 0:
                in_i += line[i]
        out_i = 0
        for j, line in enumerate(f[i]):
            # 不能计算反向暗流
            if self.__edges[i][j] > 0:
                out_i += line
        return in_i - out_i

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

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

    def to_flow_height_dot(self, flow, h):
        dot_s = 'digraph s {\n\tlayout=fdp\n\tnode [shape = box]\n'
        for i, v in enumerate(self.__vertices):
            excess = self.get_excess(flow, i)
            if i != self.__s and excess < 0:
                # raise RuntimeError('错误')
                print("-----------------------------")
            dot_s += f'\t"{v}"[pos="{self.__pos[i]}";label="{v}/{h[i]}/{excess}"];\n'
        for i, e in enumerate(self.__edges):
            for t, weight in enumerate(e):
                if weight == 0 and flow[i][t] == 0:
                    continue
                edge = f'\t\"{self.__vertices[i]}\"->"{self.__vertices[t]}"'
                dot_s += edge
                f = flow[i][t]
                dot_s += f'[label="{f}/{weight}";'
                # 反向的暗流
                if weight == 0:
                    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.push_relabel import FlowNetwork


class PushRelabelTestCase(unittest.TestCase):
    def test_push_relabel(self):
        # 做一张图
        vertices = ['S', '2', '3', '4', '5', '6', '7', 'T']
        # 设计容量
        edges = [
            [0, 10, 5, 15, 0,  0,  0,  0],
            [0, 0,  4,  0, 9,  15,  0,  0],
            [0, 0,  0,  4, 0,  8,  0,  0],
            [0, 0,  0,  0, 0,  0, 30,  0],
            [0, 0,  0,  0, 0, 15,  0, 10],
            [0, 0,  0,  0, 0,  0, 15, 10],
            [0, 0,  6,  0, 0,  0,  0, 10],
            [0, 0,  0,  0, 0,  0,  0,  0]
        ]

        pos = ["0,0!", "2,1!", "2,0!", "2,-1!", "4,1!", "4,0!", "4,-1!", "6,0!"]
        fn = FlowNetwork(vertices, edges, 0, 7, pos)

        print(fn.to_dot())

        flow = fn.push_relabel()
        print(fn.to_flow_dot(flow))

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

  测试执行了52次循环，最终结果如下：