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

看板Grad-ProbAsk作者hopward (hopward)時間7年前 (2016/08/31 09:57)推噓3(3推 0噓 6→)

留言9則, 3人參與討論串1/1

昨天上完課回家看書的時候發現跟原先認知有點出入，我原本是以為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

08/31 11:24, , 1^F

08/31 11:24, 1^F

→

exilelast

08/31 11:26, , 2^F

08/31 11:26, 2^F

→

exilelast

08/31 11:29, , 3^F

08/31 11:29, 3^F