1.Push-Relabel演算法思想
對於一個網路流圖: 該演算法直觀可以這樣理解，先在源節點處加入充足的流(跟源節點ss相連的所有邊的容量之和)，然後開始按一定規則進行流滲透，一個邊一個邊的向匯點滲透，直到沒法再滲透（類似於Ford-Fulkerson演算法中找不到增廣路徑了），那麼這時再把一些剩餘的流回收到源節點ss就可。 主要分為兩個步驟：push和relabel。push表示從所有節點找出一個存水量大於0的節點uu，將它所存的水儘可能推向與它相鄰的節點vv。要實現該push的操作必須滿足下麵條件：該點存水量e(u)>0e(u)>0，節點uu的高度大於節vv的高度。本次推送的流值(u,v).f=mine(u),(u,v).capacity(u,v).f=mine(u),(u,v).capacity,(u,v).capacity(u,v).capacity為邊 edge(u,v)edge(u,v)的當前容量，這個值在推進過程中會一直變換。relabel表示某一個節點存水量大於0但水流不出去時，我們對該節點高度增加1，這就是所謂relabel操作，使得該節點的存水量流入比它低的節點。一開始的時候我們設定源節點高度為N,此處N為節點數N,此處N為節點數，其他所有節點高度為0，並且匯節點的高度固定為0，其他節點高度在演算法執行過程中高度hh會改變。
演算法步驟： 1.初始化前置流：將與源點s相連的管道流量f(0,i)設為該管道的容量，即 f(0,i)=c(0,i)；將源點s的高度h(0)=V，(V表示圖的頂點個數)，其餘頂點高度h(i)=0；將源的點餘量e(0)設為源容量減去源的流出量，即e(0)=-∑f(0,i)=-∑c(0,i)，與源s相連的點餘量設為該點的流入量e(i)=c(0,i)，其餘點都為0。
2.搜尋是否有節點的點餘量e(u)>0e(u)>0，如果存在，表示要對該點進行操作——重標記或者壓入流：檢查與該點u全部的相鄰點v，若該點比它相鄰點的高度大h(u)>h(v),該管道的當前容量為c(u,v)c(u,v)，將該點u的餘量以最大方式壓入該管道delta=min(e(u),c(u,v))delta=min(e(u),c(u,v)), 然後對節點u,v的餘量e、邊(u,v)的容量進行相應的進行減加操作；如果找不到高度比自己低的相鄰節點v,則對節點u的高度增加1，即h(u)=h(u)+1h(u)=h(u)+1。如此繼續進行Push操作。以上的重標記或壓入流操作迴圈進行，直至該點的餘量e(u)為0。 3.重複第2步，直找不到餘量大於0的節點，停止演算法，最後輸出匯點t的餘量e(t), 該值就是最後所求的最大流。最小割。
2.Push-Relabel演算法原理示意圖
給定的網路流圖如下：
第一步：初始化操作：
第一次Push不成功，進行Relabe
第二次Push，成功
繼續Push
至此結束。
3.Push-Relabel演算法具體例項
求解下面網路流圖的最大流：
1.Push-Relabel演算法思想
對於一個網路流圖: 該演算法直觀可以這樣理解，先在源節點處加入充足的流(跟源節點ss相連的所有邊的容量之和)，然後開始按一定規則進行流滲透，一個邊一個邊的向匯點滲透，直到沒法再滲透（類似於Ford-Fulkerson演算法中找不到增廣路徑了），那麼這時再把一些剩餘的流回收到源節點ss就可。 主要分為兩個步驟：push和relabel。push表示從所有節點找出一個存水量大於0的節點uu，將它所存的水儘可能推向與它相鄰的節點vv。要實現該push的操作必須滿足下麵條件：該點存水量e(u)>0e(u)>0，節點uu的高度大於節vv的高度。本次推送的流值(u,v).f=mine(u),(u,v).capacity(u,v).f=mine(u),(u,v).capacity,(u,v).capacity(u,v).capacity為邊 edge(u,v)edge(u,v)的當前容量，這個值在推進過程中會一直變換。relabel表示某一個節點存水量大於0但水流不出去時，我們對該節點高度增加1，這就是所謂relabel操作，使得該節點的存水量流入比它低的節點。一開始的時候我們設定源節點高度為N,此處N為節點數N,此處N為節點數，其他所有節點高度為0，並且匯節點的高度固定為0，其他節點高度在演算法執行過程中高度hh會改變。
演算法步驟： 1.初始化前置流：將與源點s相連的管道流量f(0,i)設為該管道的容量，即 f(0,i)=c(0,i)；將源點s的高度h(0)=V，(V表示圖的頂點個數)，其餘頂點高度h(i)=0；將源的點餘量e(0)設為源容量減去源的流出量，即e(0)=-∑f(0,i)=-∑c(0,i)，與源s相連的點餘量設為該點的流入量e(i)=c(0,i)，其餘點都為0。
2.搜尋是否有節點的點餘量e(u)>0e(u)>0，如果存在，表示要對該點進行操作——重標記或者壓入流：檢查與該點u全部的相鄰點v，若該點比它相鄰點的高度大h(u)>h(v),該管道的當前容量為c(u,v)c(u,v)，將該點u的餘量以最大方式壓入該管道delta=min(e(u),c(u,v))delta=min(e(u),c(u,v)), 然後對節點u,v的餘量e、邊(u,v)的容量進行相應的進行減加操作；如果找不到高度比自己低的相鄰節點v,則對節點u的高度增加1，即h(u)=h(u)+1h(u)=h(u)+1。如此繼續進行Push操作。以上的重標記或壓入流操作迴圈進行，直至該點的餘量e(u)為0。 3.重複第2步，直找不到餘量大於0的節點，停止演算法，最後輸出匯點t的餘量e(t), 該值就是最後所求的最大流。最小割。
2.Push-Relabel演算法原理示意圖
給定的網路流圖如下：
第一步：初始化操作：
第一次Push不成功，進行Relabe
第二次Push，成功
繼續Push
繼續Push
繼續Push
至此結束。
3.Push-Relabel演算法具體例項
求解下面網路流圖的最大流：