[理工] 演算法 ford-fulkerson 的cancellation
作者: b4824583 (阿丰) 2017-12-07 21:38:26
不好意思，想問一下，如果今天我找到這樣的augement path，s>a>b>t
演算法會怎麼執行cancelation?
感覺選錯argument path就死結了
我上網看影片，看文章甚至課本，都還是不太懂
作者: can18 (18號) 2017-12-07 22:02:00
選到的 augementing path 一定可以增加流量(s,a) 剩餘流量為0 所以這個邊不會在residual graph 出現自然不會找這條為augmenting path
作者: b4824583 (阿丰) 2017-12-08 00:23:00
還是不是很理解，不過謝謝喔
作者: TMDTMD2487 (ㄚ冰) 2017-12-08 08:06:00
如果你一開始如圖選擇sabt，那你的residual network上一定不會有這條路徑，除非你一開始sabt沒有把他流滿你看你的residual, sabt這段capacity有人是0, 你就不可能選到如果sabt每個capacity都大於0, 那你當然可以選, 然後再一次把它調整成新的residual (一開始就把sabt流到極限滿, 那你會扣掉flow形成新的residual, 如此一定會有人的capacity會是0, 就不會重複的找到一樣的flow
作者: b4824583 (阿丰) 2017-12-09 17:40:00
好的，我想想