AI
推荐
模板社区
专题
登录
免费注册
首页
流程图
详情
网络流最大流 EdmondsKarp算法 手动调试详解
2017-11-08 14:33:54
0
举报
分享方式
仅支持查看
网络流最大流 EdmondsKarp算法 手动调试详解
计算机科学与技术
算法
程序设计
Edmonds-Karp算法
模板推荐
作者其他创作
大纲/内容
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
收藏
立即使用
循环神经网络rnn模型
收藏
立即使用
网络流最大流 EdmondsKarp算法 手动调试详解
魔术师LYX[魔術師]
职业：暂无
去主页
Collect
Get Started
手动导入订单流程
Collect
Get Started
RocketMQ 由浅入深详解
Collect
Get Started
Docker由浅入深详解
Collect
Get Started
调试模式
评论
0
条评论
下一页
Document
