預流推進

出自 MBA智库百科(https://wiki.mbalib.com/)

　　預流推進為網路流演算法中的一種較為高效的一種演算法，是最高標號法的基礎。可以想象在一個自來水管網的源頭儘可能多的註入水流之後，最多有多少水可以流到匯點去，由網路的各個節點和管道來約束流量。將每個節點都看成一個水站，他的通過能力是有限的不能通過的水只能退回去。

　　預流推進演算法給每一個頂點一個標號h(v)，表示該點到t的最短路（在殘量網路中）。

　　第一步hights()過程，就是BFS出初始最短路，計算出每一個結點的h(v)。//可以看作是匯點有“吸力”，使每個結點有不同的負壓，在“負壓”作用下把來自源點的流吸過去。

　　預流推進演算法的特征是運用了預流來加快運算。預流說明圖中的結點(除s, t)，僅需要滿足流入量 >= 流出量。其中流入量>流出量的結點，我們稱之為活動結點。/*換句話說就是有流可吸，還沒吸到地方。*/我們的演算法就是不斷地將活動結點，變為非活動結點，使得預流成為可行流。

　　演算法過程prepare()，即首先將與s相連的邊設為滿流，並將這時產生的活動結點加入隊列Q。這是演算法的開始。

　　以後便重覆以下過程直到Q為空：

　　(1).選出Q的一個活動結點u。並依次判斷殘量網路G'中每條邊(u, v)，若h(u) = h(v) + 1，則順著這些邊推流，直到Q變成非活動結點（不存在多餘流量）。(Push推流過程)//同時把所有v加入活動結點的隊列。

　　(2).如果u還是活動結點。則需要對u進行重新標號：h(u) = min{h(v) + 1}，其中邊(u,v)存在於G' 中。然後再將u加入隊列。(reCalc過程)//後面都滿流時就吸不動了，負壓自然也要重新計算。

　　可以證明，通過以上演算法得到的結果就是最大流。

　　顯然每次迴圈後標號和殘量網路都是相容的。演算法結束時Q為空，只可能是沒有活動結點。因為一開始就把從源所有的流推了出來，只可能是要麼能夠推到匯要麼最後退回源。顯然，一開始源的標號最高，退回源說明源匯之間已被切斷，否則總能殺出一條增廣路來。

　　如果該演算法的Q是標準的FIFO隊列，則時間複雜度為(n2m)，/*最高標號不會超過n（超過時必無到匯的路徑），所以n個點每個最多重新標號n次，兩次標號之間m條邊每條最多推流一次。*/如果是優先隊列，並且標號最高的點優先的話，我們就得到了最高標號預流推進演算法，其時間複雜度僅為(n2sqrt(m))，/*複雜度分析進行中……*/算是比較快的最大流演算法了。