Push-Relabel算法|集1（简介和插图）-yiteyi-C++库

给出一个图，它表示一个流动网络，其中每条边都有一个容量。也给出了两个顶点来源 “s”和下沉 “t”在图中，找出从s到t的最大可能流量，并满足以下约束条件：

null

（a） 边缘上的流量不会超过边缘的给定容量。

b）除了s和t之外，每个顶点的输入流都等于输出流。

例如，从CLSR书中考虑下面的图表。

上图中的最大可能流量为23。

我们讨论过福特-富尔克森算法它使用增广路径来计算最大流量。

推重标记算法

Push-Relabel算法比Ford-Fulkerson算法更有效。在这篇文章中，Goldberg的“通用”最大流算法在 O（V） ^2. （E） 时间这个时间复杂度比O（E）好 ^2. 五）这是Edmond Karp算法（Ford Fulkerson基于BFS的实现）的时间复杂度。存在一种适用于O（V）的基于推-重新标记方法的算法 ^3. )这比这里讨论的还要好。

与福特·富尔克森的相似之处

和福特·富尔克森一样，Push-Relabel也适用于剩余图（流网络的剩余图是一个表示额外可能流的图。如果剩余图中有一条从源到汇的路径，则可以添加流）。

与福特·富尔克森的不同之处

Push-relabel算法以更本地化的方式工作。push-relabel算法一次只在一个顶点上工作，而不是检查整个剩余网络以找到一条增广路径（来源：CLRS Book）。
在Ford Fulkerson，每个顶点（源和汇除外）的总流出和总流入之间的净差保持为0。Push-Relabel算法允许流入量在达到最终流量之前超过流出量。在最终流量中，除源和汇外，其他所有流量的净差值均为0。
时间复杂度方面效率更高。

推拉算法（考虑流体流动问题）背后的直觉是，我们认为边是水管，节点是关节。水源被认为处于最高水位，将水输送至所有相邻节点。一旦节点有多余的水，它就会推动水到一个较小的高度节点。如果水在某个顶点被局部截留，则该顶点为 重新贴标签 这意味着它的高度增加了。

下面是一些有用的事实，在我们进行算法之前要考虑。

每个顶点都有一个高度变量和一个过剩流量。身高用于确定顶点是否可以将流推送到相邻顶点（顶点只能将流推送到高度较小的顶点）。 过剩流量 是流入顶点的总流量减去流出顶点的总流量之差。
```
     Excess Flow of u = Total Inflow to u - 
                        Total Outflow from u
```
比如福特·富尔克森。每条边都与一个流（指示电流）和容量

以下是完整算法的抽象步骤。

Push-Relabel Algorithm 
1) Initialize PreFlow : Initialize Flows 
   and Heights 

2) While it is possible to perform a Push() or 
   Relablel() on a vertex
   // Or while there is a vertex that has excess flow
           Do Push() or Relabel()

// At this point all vertices have Excess Flow as 0 (Except source
// and sink)
3) Return flow.

Push-Relabel算法有三个主要操作

初始化预流（） 它初始化所有顶点的高度和流动。

Preflow() 
1) Initialize height and flow of every vertex as 0.
2) Initialize height of source vertex equal to total 
   number of vertices in graph.
3) Initialize flow of every edge as 0.
4) For all vertices adjacent to source s, flow and  
   excess flow is equal to capacity initially.

推用于从流量过大的节点生成流量。如果一个顶点有多余的流量，并且有一个高度较小的相邻点（在残差图中），我们将流量从顶点推到高度较低的相邻点。通过管道（边缘）的推动流量等于边缘的最小过剩流量和容量。
Relabel（） 当顶点流量过大且相邻顶点均不在较低高度时，使用该操作。我们基本上增加了顶点的高度，这样我们就可以执行push（）。为了增加高度，我们选择最小相邻高度（在残差图中，即我们可以添加流的相邻高度）并向其添加1。

注意，上述操作是在残差图上执行的（如福克森 ).

插图： 这

每当我们从顶点u向v推送或添加流时，我们都会在残差图中执行以下更新： 1）我们从u到v的边的容量中减去流量。如果边的容量变为0，则边不再存在于残差图中。 2）我们增加了从v到u的边缘容量。

For example, consider two vertices u an v.

In original graph
        3/10
   u ---------> v
    3 is current flow from u to v and
    10 is capacity of edge from u to v.

In residual Graph, there are two edges corresponding
to one edge shown above.
         7
   u ---------> v

         3
   u <--------- v

初始给定流图。
.
在预流操作之后。在剩余图中，从A到S有一条容量为3的边，而从S到A没有边。
.
高亮显示的顶点会重新标记（高度变为1），因为它有多余的流量，并且没有高度较小的相邻顶点。新高度等于相邻高度的最小值加1。在剩余图中，有两个相邻的顶点A，一个是S，另一个是B。S的高度是4，B的高度是0。这两个高度的最小值为0。我们取最小值，再加上1。
.
高亮显示的顶点有多余的流动，并且相邻顶点的高度较低，因此会发生push（）。顶点A的过量流量为2，边（A，B）的容量为1。因此，推动流量为1（至少两个值）。
.
高亮显示的顶点会重新标记（高度变为1），因为它有多余的流量，并且没有高度较小的相邻顶点。
.
高亮显示的顶点有多余的流，并且相邻顶点的高度较低，因此flow（）从B推到T。
.
高亮显示的顶点会重新标记（高度变为5），因为它有多余的流量，并且没有高度较小的相邻顶点。
.
高亮显示的顶点有多余的流动，并且相邻顶点的高度较低，因此会发生push（）。
.
高亮显示的顶点会重新标记（高度增加1），因为它有多余的流量，并且没有高度较小的相邻顶点。