知识卡片
残量网络允许撤回部分流量
对实际边 u→v,正向残量为 c−f,反向残量为 f;残量路径允许增加尚有容量的正向流,也允许减少此前的反向流。路径瓶颈为各残量最小值,按该值更新各边,保持容量与中间点守恒。
没有源到汇残量路径时,当前可行流为最大流。整数容量下每次正增广至少1,因此朴素Ford-Fulkerson有限终止;任意无理实数容量和任意增广策略不能无条件保证有限终止。
228的03379–03384区分前向剩余容量和反向可撤回流;路径前驱需保存边方向,处理时对正向加流、反向减流。使用BFS寻找按边数最短的增广路径是Edmonds-Karp。反向增广会调整先前流量,因此不是完全不撤销先前决策。
230给出整数容量Ford-Fulkerson以邻接结构搜索时 O(E·F) 的常见界,其中F为最大流整数值;Edmonds-Karp用BFS得到 O(VE²) 上界,与容量数值大小无关。实际搜索成本还依图表示和初始化而定。
231的03385–03387用容量与反对称净流矩阵、循环队列和BFS;空间为 O(V²),适合特定规模与密度。容量、流值、总流及残量算术需检查溢出;输入边、源汇及队列边界需验证,性能应在目标环境测量。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 残量网络允许撤回部分流量
- · 解决方案
- · 分析
- · 优化
原书出处 · 4 处
- · 查看原书依据
增广路,这条增广路通过一个s到t的网络,并且这条增广路上可以增加更多的流。如果不能再找到一条增广路,那么算法终止。最大流最小割理论(Ford-Fulkerson,1962)保证没有负流和负容量限制,Ford-Fulkerson肯定能够终止并且能够找出网络中的最大流。 图 8-3 Ford-Fulke
- · 查看原书依据
广度优先搜索(见第6章)。 图 8-5 Search的功能 例8-3的流网络是使用深度优先搜索寻找增广路得到的结果,例8-2是其实现。路径使用栈来存储顶点。我们从栈中弹出一个顶点u,然后找到u的一个未访问顶点v,且满足这样两个条件:(i)边(u,v)是一条前向边并且还有多余的容量;(ii)边(v,u
- · 查看原书依据
Edmonds-Karp算法),性能为O(V*E2)。广度优先搜索能够在O(V+E)的时间内找到最短的增广路,如果顶点比边数少很多,那么实际性能是O(E)。Cormen等(2001)曾证明基于广度优先搜索的Ford-Fulkerson算法是按照长度来依次求出增广路的,而不是像深度优先搜索那样花费大量
- · 查看原书依据
优化的Ford-Fulkerson实现