知识卡片

普通读书笔记卡 · 3646.g.6 · 生成模型:未记录

费用流的反向残量边带负费用

理解等级:中级

若原边单位费用为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算法中所看到的那样,我们必须要