在前幾天的文章里面，我們講到求解最大流的關鍵是找到增廣路，并且單獨介紹了一個求增廣路的Ford-Fulkerson算法，也叫做標號法。事實上還有許多別的求增廣路的算法，今天我們就再介紹一個“最短增廣路”算法。

最短增廣路的思想其實很簡單，既然需要找一條增廣路來優(yōu)化，那就直接找最短的那條增廣路吧。

首先介紹兩個重要概念，一個叫殘留量：給定容量網(wǎng)絡G(V, E)及可行流f，弧上的殘留容量記為c'(u, v)= c(u, v)–f(u,v)。每條弧的殘留容量表示該弧上可以增加的流量。因為，從頂點u到頂點v流量的減少，等效于頂點v到頂點u流量增加，所以每條弧上還有一個反方向的殘留容量c'(v,u) =–f(u,v)。由殘留量組成的網(wǎng)絡叫做殘留網(wǎng)絡，下面給個例子：

上圖a中的兩個數(shù)字分別表示弧的容量和已經(jīng)用掉的容量。

注意b圖，它里面各個點之間其實有一個層次關系，比如Vs是第0級，V1和V2是第一級，等等。下面是網(wǎng)絡節(jié)點按級劃分的結果：

對殘留網(wǎng)絡分層后，刪去比目的點Vt層次更高的頂點和與目的點Vt同層的頂點，然后刪去與這些頂點關聯(lián)的弧，再刪去從某層頂點指向同層頂點和低層頂點的弧，所剩的各條弧的容量與殘留網(wǎng)絡中的容量相同，這樣得到的網(wǎng)絡是殘留網(wǎng)絡的子網(wǎng)絡，稱為層次網(wǎng)絡。

解釋一下構造層次網(wǎng)絡的時候為什么要這么刪除多余的邊：刪除比Vt層次更高，以及同級別的點的原因很簡單：Vt是目的點，不允許有從Vt中流出的流量。刪除指向同層以及底層的邊是因為我們要找的是最短增廣路，留著這些邊會把增廣路邊長。有人可能會問，少考慮了一些潛在的增廣路，不會對最終結果有影響么？別擔心，當前的增廣路被處理完之后，在下一輪循環(huán)里就不再考慮了，此時這些上一輪沒有考慮到的、仍舊有剩余流量的邊就會被考慮到的。

不知道大家注意到?jīng)]有，層次網(wǎng)絡中任何一條連接源點Vs和目的點Vt的通路都是一條增廣路，并且是最短的增廣路。

知道尋找最短增廣路之后問題就簡單了，找到之后優(yōu)化它，然后重新找找看還有沒，還有增廣路的話繼續(xù)優(yōu)化，直到不存在增廣路為止。

n