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

[hopward (hopward)]

昨天上完課回家看書的時候發現跟原先認知有點出入，我原本是以為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，請問我目前看到書上這樣的見解正確嗎，麻煩大大幫忙解惑一下感恩。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.104.232
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1472608638.A.C51.html
推 exilelast: 我覺得你的步驟沒有錯，依照你的步驟可以解出MAX FLOW
→ exilelast: 書上只是同時畫出原圖跟residant network圖做對照而已
→ exilelast: 畢竟residant network不能代表原圖的狀況，只能幫你找
→ exilelast: MAX FLOW 而已
推 w181496: 找到增廣路後原圖或residual network都會扣掉這條的流量
→ w181496: (原圖能流的變少 相當於residual network容量變小)
→ w181496: 所以原圖轉residual network和原本residual network去找
→ w181496: max flow其實都一樣吧
推 h42318: 你的認知沒錯 解答只是多幫你畫了原圖