殘餘網路（residual graph）

假設你已經導引了一些水，想知道還剩哪些動作。可用的動作有兩類：沿著仍有空間的管子再推一些，或把先前送出的水沿反方向推回來以撤銷。殘餘網路正是記錄部分流之後這些剩餘選項的帳本——而第二類，撤銷的能力，正是讓流演算法正確的微妙要素。

給定網路 G 上的流 f，殘餘網路 Gf 有相同的頂點，且對每條容量 c、流量 f(u, v) 的原邊 (u, v)，最多有兩條殘餘邊。一條前向殘餘邊 u -> v，殘餘容量為 c(u, v) - f(u, v)，代表你還能填的剩餘空間。一條後向殘餘邊 v -> u，殘餘容量為 f(u, v)，代表你能藉改道撤銷的流量。例如若 c(u, v) = 5 且 f(u, v) = 3，則 Gf 有殘餘容量 2 的 u -> v 與殘餘容量 3 的 v -> u。殘餘容量為零的邊乾脆略去。要改進一個流，就在 Gf 中找一條從 s 到 t、殘餘容量全為正的路徑並沿之推送；在後向邊上推送，意味著在那裡減少原本的流。

殘餘網路是每個增廣路徑演算法的引擎。增廣路徑、福特-富爾克森、埃德蒙茲-卡普與 Dinic 全都作用在 Gf 而非 G 上。後向邊是關鍵的轉折：少了它們，貪婪的推送可能把自己逼進死角而無從改道，於是你可能停在真正最大值之前。有了它們，你總能撤銷一個糟糕的決定，這正是讓方法達到最佳的原因。殘餘網路還順帶交出最小割：當 Gf 中不再有 s-t 路徑時，仍能從 s 抵達的頂點構成某個最小割的 s 側。