大家好，最近在學Maximum Flow時學到這個演算法，
這個演算法說到，在每次更新路徑(流量)的時候，
要選擇最最小的那一條，我看了手邊的範例，
無法理解他所說的最小的那一條是怎麼算出來的，
http://tinyurl.com/azefzfp
這個是我在網路上找到的一個範例投影片，
第五頁的部分，他的選擇是 s -> 3 -> 5 -> 4 -> t 流量是6
為什麼不選擇 s -> 3 -> 2 -> 4 -> t 流量是2呢?
謝謝

s -> 3 -> 5 -> 4 -> t 中經過的殘餘容量是10 7 6 10裡面最小的是 5 -> 4 的 6. 他說的最小是這個你看 5->4 那一條的箭頭特別粗

你記錯前提了，Ford-Fulkerson 沒有要求要最小的那條看了樓上才知道原來誤會是在那裡 :p

那請問可以走我說的那一條嗎?經過1F的說明，我現在的認知是，只要任選一條走S到T那一條路徑的流量是當中最小的就可以了?那另外請問，這個例子當中的，min cut是否是指

可以，但你上面這句應該是錯的。

找出max flow之後，s點還可以走到3，而s和3連接到其他的點所構成的邊就是min cut

最小是指,path可增加的流量,是所有經過edge中剩餘流量最小的

也就是S到2和3到5 這兩條?t大我解你所說的，我上面用字不精確造成誤會

正確

相當感謝