知识卡片
费用流的反向残量边带负费用
若原边单位费用为c,增加流量费用为+c,撤回已有流量的反向残量边费用为−c。逐次最短增广需在残量网络正确求最短费用路径,并维护可行流和要求的目标流量;可用势函数将适用情况下的约化费用转为非负,再使用Dijkstra,或采用支持负权的最短路方法。
03391–03392直接以优先队列处理可能为负的反向费用、限制候选距离非负并在汇点出队时提前结束;没有展示势函数,不能据此对一般费用网络保证最短增广路。费用总和和距离还需防溢出。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
最小开销的增广路会发生什么呢?我们已经讨论过一些贪心算法(例如第6章中构造最小生成树的Prim算法)就是不断地选择最小开销的方向进行扩展,也许这样的方法能够在这里可行。 为了寻找最小开销的增广路,我们就不能拘泥于单纯使用广度优先搜索或者是深度优先搜索。正如我们在Prim算法中所看到的那样,我们必须要
参考来源
- 位置:《算法技术手册》第8章《在增广路上的深入思考》(spine1637;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1600.html;u237-ch08-007)。
- 结论依据:237全文及03391–03393完整代码和运输示例实读。
- 原始内容:最小开销的增广路会发生什么呢?我们已经讨论过一些贪心算法(例如第6章中构造最小生成树的Prim算法)就是不断地选择最小开销的方向进行扩展,也许这样的方法能够在这里可行。 为了寻找最小开销的增广路,我们就不能拘泥于单纯使用广度优先搜索或者是深度优先搜索。正如我们在Prim算法中所看到的那样,我们必须要