落絮飞雁的个人网站

顺流而下,把梦做完

图论:最小费用流与Bellman-Ford算法

最小传输费用问题


网络中有两台计算机s和t,现在每秒钟要从s传输大小为F的数据到t。该网络中一共有N太计算机,其中一些计算机之间连有一条单向的通信电缆,每条通信电缆都有对应的一秒内传输的最大数据量。此外,每条电缆还有对应的传输费用,即单位传输费用为d的通信电缆传输大小为x的数据,需要费用为dx。请问传输数据的最小费用。

问题可以转换为一个有向图(计算机为各顶点,传输电缆为边)。每条边有其容量c(e)和费用d(e)。问题可以转换为在保证从s向t有大小为F的流的情况下,使得总费用最小。就是最小费用流问题(最大流情况下每条边添加费用F,求最小值)。

贪心增广,参与网络中的反向边费用应该是原边费用的相反数。需要注意最小费用流不能使用Dijkstra算法因为有负权边。可以使用Bellman-Ford算法

Bellman-Ford模板:

可以通过数学归纳法证明算法为最小费用流(即证明残余网络中没有负圈),证明过程可以详见MIT讲义

特殊情况

 

  • 对于流量任意
    如果需要计算包含负权边的图中流量任意但费用最小的流。可以根据最小流算法中h[i+1](v)>=h[i](v)的性质,在h[i](t)<0时进行增广。
  • 对于费用为负
    存在负权边需要用Bellman-Ford算法。存在负圈可以利用算法找到负圈并在负圈上尽量增广。通过变形避免负权边的算法(每次增广时如边数相等,通过对所有边费用加上合适常数将边转成非负数)只适用部分情况。

参考


原文转自:图论:最小费用流与Bellman-Ford算法|落絮飞雁的个人网站
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。
  1. linanwy说道:

    同学,你的代码被转义了,请看第二十五行

    1. 落絮飞雁说道:

      谢谢,已经改了。