[理工] 演算法 Ford-Fulkerson 流程問題

作者: hopward (hopward)   2016-08-31 09:57:16
昨天上完課回家看書的時候發現跟原先認知有點出入,我原本是以為Ford Fulkerson是先在原圖上找一條augmenting path,接著根據目前找到的圖找他的residual network,然後再在residual network中找augmenting path,然後再找目前這個residual network的residual network以此類推。
但看到課本上的例題的詳解後
http://i.imgur.com/K3917xj.jpg
http://i.imgur.com/fbFIynG.jpg
http://i.imgur.com/woRB5It.jpg
發現他好像是在找完residual network的augmenting path之後,再回原圖繼續找原圖目前剩餘capacity的augmenting path,請問我目前看到書上這樣的見解正確嗎,麻煩大大幫忙解惑一下感恩。
作者: exilelast (exile)   2016-08-31 11:24:00
我覺得你的步驟沒有錯,依照你的步驟可以解出MAX FLOW書上只是同時畫出原圖跟residant network圖做對照而已畢竟residant network不能代表原圖的狀況,只能幫你找MAX FLOW 而已
作者: w181496 (Kaibro)   2016-08-31 14:03:00
找到增廣路後原圖或residual network都會扣掉這條的流量(原圖能流的變少 相當於residual network容量變小)所以原圖轉residual network和原本residual network去找max flow其實都一樣吧
作者: h42318 (五兩三)   2016-09-01 17:15:00
你的認知沒錯 解答只是多幫你畫了原圖

Links booklink

Contact Us: admin [ a t ] ucptt.com