网络流最大流 EdmondsKarp算法 手动调试详解
2017-11-08 14:33:54 0 举报网络流最大流 EdmondsKarp算法 手动调试详解
作者其他创作
大纲/内容
20
10
1
30
2
顶点
preVertex
flow
-1
无穷大
40
3
4
所以BFS递归搜索不到任何增广路径EK算法结束
更新完毕后各个点的preVertex值和flow值如下
src为3找到它的所有下级可达点 4没有顶点的preVertex都是-1(点未知)
当前残余流量图
src为3找到它的所有下级可达点 没有结束
第一次寻找增广路径更新残余流量图
src为4结束
更新后残余流量图
所以BFS递归搜索到的增广路径为[1-2-4]该路径上的流量为20更新残余流量图
原残余流量图
所以BFS递归搜索到的增广路径为[1-2-3-4]该路径上的流量为10更新残余流量图
第二次寻找增广路径更新残余流量图
最后得到的残余流量图
第四次寻找增广路径更新残余流量图
所以BFS递归搜索到的增广路径为[1-4]该路径上的流量为20更新残余流量图
第三次寻找增广路径更新残余流量图
每次寻找增广路径前初始化preVertex全为-1 ，flow全为无穷大寻找增广路径依赖残余流量图
src为3找到它的所有下级可达点 分别为4没有点的preVertex是-1(点未知)
所以最后得到原图的最大流量MaxFlow = 20+20+10 = 50
收藏
职业：暂无
0 条评论
下一页
