知识卡片

普通读书笔记卡 · 3646.d.7.a.1.a

最短增广总耗时界

理解等级:中级

Edmonds–Karp 每轮用 BFS 选择边数最少的增广路。临界边是该路上达到瓶颈、增广后残余容量变为 0 的边;每轮至少有一条临界边。

同一有向边再次成为临界边前,其尾点到源点的 BFS 距离至少增加 2,而有限距离最多为 |V|−1,所以每条边至多 O(V) 次临界。残量图至多 O(E) 条边,增广轮数因而至多 O(VE);每轮 BFS 和沿路更新均为 O(E),相乘得到总时间 O(VE²)。

这张卡片看不懂?

已有反馈 · 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)