知识卡片
最短增广总耗时界
Edmonds–Karp 每轮用 BFS 选择边数最少的增广路。临界边是该路上达到瓶颈、增广后残余容量变为 0 的边;每轮至少有一条临界边。
同一有向边再次成为临界边前,其尾点到源点的 BFS 距离至少增加 2,而有限距离最多为 |V|−1,所以每条边至多 O(V) 次临界。残量图至多 O(E) 条边,增广轮数因而至多 O(VE);每轮 BFS 和沿路更新均为 O(E),相乘得到总时间 O(VE²)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 最短增广总耗时界
原书出处 · 1 处
- 第24章 最大流 · 查看原书依据
the total running time of the Edmonds-Karp algorithm is O(VE2). Exercises 24.2-1 Prove that the summations in equation (24.6) equal the summations on the right-hand side of equation (24.5). 24.2-2 In Figure 24.1(b)
参考来源
- 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[40000,45000))。
- 结论依据:定理24.8给出O(VE)次增广,紧接文字给出O(VE²)总时间。
- 原始内容:the total running time of the Edmonds-Karp algorithm is O ( VE 2 ). Exercises 24.2-1 Prove that the summations in equation (24.6) equal the summations on the right-hand side of equation (24.5). 24.2-2 In Figure 24.1(b)