最大流量问题.DOCVIP

最大流量問題 原圖 方法 找一條從起點到終點且剩餘流通量0的路徑（若找不到，則已經找到最大流量，演算法完成） 在步驟1.所找到的路徑上，選擇剩餘流通量最小者，以c*表示，將c*的值累加到最大流量 在步驟1.所找到的路徑上，每條邊的剩餘流通量減少c*，邊的反方向增加c* 回到步驟1. 步驟1　分配流量5於O→B→E→T，得下列網路 步驟2　分配流量3於O→A→D→T，得下列網路 步驟3　分配流量1於O→A→B→D→T，得下列網路 步驟4　分配流量2於O→B→D→T，得下列網路 步驟5　分配流量1於O→C→E→D→T，得下列網路 步驟6　分配流量1於O→C→E→T，得下列網路 步驟7　分配流量1於O→C→E→B→D→T，得下列網路（完成） 步驟8　比對目前流通容量與原流通容量的「出發端」，就可以知道各頂點流出量，每個頂點流入＝流出 A：計算結果 B：原圖 C：解答