知识卡片
最宽增广路最大化本轮瓶颈
最宽增广路是在所有残量网络源汇增广路中,使路径最小残余容量最大的那条。
它优化单轮可增广量,区别于Edmonds–Karp按最少边数选路。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第24章 最大流 · 查看原书依据
a widest augmenting path: an augmenting path with the greatest residual capacity. Assume that G = (V, E) is a flow network with source s and sink t, that all capacities are integer, and that the largest
参考来源
- 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[55000,60000))。
- 结论依据:问题24-6明确定义最宽增广路,并对照最短增广路策略。
- 原始内容:a widest augmenting path : an augmenting path with the greatest residual capacity. Assume that G = ( V , E ) is a flow network with source s and sink t , that all capacities are integer, and that the largest