[理工] 算法 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