網路流 Edmonds-Karp 最大流

想像一張自來水管網：從水廠出發，經過好幾條粗細不同的管子，最後匯到你家水龍頭——每條管子每秒能過多少水都有上限。 最大流問題（Maximum Flow）問的就是：整張網一次到底能送出多少水？現實裡到處都是這種題，像貨運排班、網路頻寬分配都能化成它。 難處在於某條看似順的路，可能卡住另一條更划算的走法，所以演算法得能「反悔」、把水退回去改道。 下面你會看到 Edmonds-Karp 一輪一輪找路、把水灌到滿的完整過程。

最大流問題（Maximum Flow）要在一張帶容量的有向圖上，求出從源點 s 到匯點 t 能同時推送的最大流量。 Edmonds-Karp 是 Ford-Fulkerson 方法的具體實作：每一輪都在「殘餘圖」上用 BFS 找一條 s→t 的最短增廣路， 沿路推送該路徑上的瓶頸容量（路徑上殘餘容量的最小值），直到 s→t 在殘餘圖中不再可達為止。 殘餘圖的關鍵直覺是反向邊：每推一次流，就在反方向開出等量的「反悔」容量——如果後面發現這條邊推錯了方向， 可以透過反向邊把流量退回去、改走別條路徑。反向邊的初始容量為 0，只有正向邊被推流之後才會出現非零的殘餘容量。