最小截集什么意思,网络流的资料( 四 ) _设备更新

至于算法的正确性，可以从理论上证明。读者可自己思考或查阅有关运筹学资料。
2.最小费用可改进路的求解
求“最小费用可改进路”是求最小费用最大流算法的关键之所在，下面我们探讨求解的方法。
设带费用的网络流图G = (V, E, C, W)，它的一个可行流是f 。我们构造带权有向图B = (V’, E’)，其中:
1、 V’ = V 。
2、若∈E，fij∈E’，权为Wij 。
若∈E，fij>0，那么∈E’，权为-Wij 。
显然，B中从S到T的每一条道路都对应关于f的一条可改进路;反之，关于f的每条可改进路也能对应B中从S到T的一条路径。即两者存在一一映射的逻辑关系。
故若B中不存在从S到T的路径，则f必然没有可改进路;不然，B中从S到T的最短路径即为f的最小费用可改进路。
现在的问题变成:给定带权有向图B = (V’, E’)，求从S到T的一条最短路径。
考虑到图中存在权值为负数的弧，不能采用Dijkstra算法;Floyd算法的效率又不尽如人意--所以，这里采用一种折衷的算法:迭代法。
设Short[k]表示从S到k顶点的最短路径长度;从S到顶点k的最短路径中，顶点k的前趋记为Last[k] 。那么迭代算法描述如下:(为了便于描述，令n = |V’|，S的编号为0，T的编号为n+1)
step 1. 令Short[k] ? +∞(1≤k≤n+1)，Short[0] ? 0 。
step 2. 遍历每一条弧。若Short[k] + < Short[j]，则令Short[j] ? Short[k] + ，同时Last[j] ? k 。倘不存在任何一条弧满足此条件则转step 4 。
step 3. 转step 2.
step 4. 算法结束。若Short[n + 1]= +∞，则不存在从S到T的路径;否则可以根据Last记录的有关信息得到最短路径。
一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n 。
3.思维发散与探索
1)可改进路费用:“递增!递增?”
设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢?
2)迭代法:“小心死循环!嘿嘿……”
迭代法会出现死循环吗?也就是说，构造的带权有向图B中会存在负回路吗?
3)费用:“你在乎我是负数吗?”
网络流图中的费用可以小于零吗?
4)容量:“我管的可不仅是弧。”
网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制:即通过此顶点的流量的上限;任务仍然是求从S到T的最小费用最大流。你能解决吗?
四、有上下界的最大流
上面讨论的网络流都只对每条弧都限定了上界(其实其下界可以看成0)，现在给每条弧加上一个下界限制Aij(即必须满足Aij≤fij) 。
例如图5-9:
弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图5-10(a)所示，流量是6;但若是加入了下界的限制，它的最大流量就只有5了，具体方案见图5-10(b) 。
那么有上下界的网络最大流怎么求呢?
一种自然的想法是去掉下界，将其转化为只含上界的网络流图。这种美好的愿望是可以实现的。具体方法如下:
设原网络流图为G = (V, E, C, A)，构造不含下界的网络流图G’ = (V’, E’, C’):
1、 V’ = V∪{S’, T’}
2、对每个顶点x，令，若h-(x)≠0，就添加一条弧，其上界为h-(x) 。
3、对每个顶点x，令，若h+(x)≠0，就添加一条弧，其上界为h+(x) 。
4、对于任何∈E，都有∈E’，其上界C’ij = Cij – Aij 。
5、新增∈E’，其上界CTS = +∞ 。
在G’中以S’为源点、T’为汇点求得最大流f’ 。若f’中从S’发出的任意一条弧是非饱和弧，则原网络流图没有可行流。否则可得原图的一个可行流f = f’ + A，即所有的fij = f’ij + Aij 。(其正确性很容易证明，留给读者完成)