山东科技大学本科毕业设计（论文）
w''(u,v):w''(u,v)?L(u)?L(v)?w(u,v)(*)
Where L(u),L(v) - calculation of G 'of the shortest path x to y when u andv the value of the label.
For the first time if the shortest path (u,v) is the flow path by the edge, then,
according to the shortest path algorithm must have
L(v)?L(u)?w'(u,v)?L(u)?w(u,v),
substituting into (*) type must
w''(u,v)?0.
If (u,v)rather than by the side of flow path, it must have:
L(v)?L(u)?w(u,v)
Into the (*)-type, there w(u,v)?0. Shows that the first amendment to w (e), against either side, there are w(e)?0, and a stream side (by side chain flow),
?0. Calculated after each iteration, if f(u,v)?0, by the there will bew(e）need to establish the network flow (u,v) edge, edge weights
w'(u,v)??w(u,v)?0 that is, the right will not be a negative side. In addition,
the calculation of each iteration with (*) fixes all the w(e), it is not difficult to prove that to each path x to y, its all the same to increase the path length
L(x)?L(y).Therefore, x and y will not be the shortest path tow(e) the
amendment changes.
36
山东科技大学本科毕业设计（论文）
附录2 中文译文
在介绍最大流问题时，我们列举了一个最大物资输送流问题。如果这个问题的已知条件还包括每条边运送单位物资的费用，那么怎样运送，才能得到最大运输量，并且输送费用最少,这便是所谓最小费用最大流问题。 在最大流的有关定义的基础上，若每条有向边除权数c(e)（表示边容量）外还有另外一个权数w(e)（表示单位流所需费用），并且已求得该网络的最大流值为F， 那么最小费用最大流问题，显然可用以 下线性模型加以描述：
min?w(e)f(e) e?E
满足 0?f(e)?c(e) ，对一切e?E
f?(e)?f?(e) ，
对一切v?Vf?(x)?F（最大流约束） （或f?(y)?F ) 解决最小费用最大流问题，一般有两条途径。一条途径是先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少。只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。 然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流。这一思路的特点是保持问题的可行性（始终保持最大流），向最优推进。另一条解决途径和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流。这个流的费用为零，当然是最小费用的。然后寻找一条源点至汇点的增流链，但要求这条增流链必须是所有增流链中费用最小的一条。如果能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻找增流链增流。这样迭代下去，直至找不出增流链，这时的流即为
37
山东科技大学本科毕业设计（论文）
最小费用最大流。这一算法思路的特点是保持解的最优性（每次得到的新流都是费用最小的流），而逐渐向可行解近（直至最大流时才是一个可行解）。 由于第二种算法和已介绍的最大流算法接近，且算法中寻找最小费用增流链，可以转化为一个寻求源点至汇点的最短路径问题，所以这里介绍这一算法。 在这一算法中，为了寻求最小费用的增流链，对每一当前流，需建立伴随这一网络流的增流网络。例如图 1 网络G 是具有最小 费用的流，边旁参数为c(e),f(e),v(e)，而图 2 即为该网络流 的增流网络G′。增流网络的顶点和原网络相同。 按以下原则建立增流网络的边：
若G中边(u,v)流量未饱，即f(u,v)?e(u,v)，则G' 中建边(u,v)，赋权w(u,v)'?w(u,v)；若G中边(u,v)已有流量，即f(u,v)?0，则G'中建边
(u,v)，赋权w(u,v)'??w(u,v)。建立增流网络后，即可在此网络上求源点
至汇点的最短路径，以此决定增流路径，然后在原网络上循此路径增流。这里，运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流。 计算中有一个问题需要解决。这就是增流网络G'中有负权边，因而不能直接应用标号法来寻找x至y的最短路径，采用其它计算有负权边的网络最短路径的方法来寻找x至y的最短路径，将大大降低计算效率。为了仍然采用标号法计算最短路径，在每次建立增流网络求得最短路径后,可将网络G的权w(e)做一次修正，使再建的增流网络不会出现负权边，并保证最短路径不至于因此而改变。下面介绍这种修改方法。 当流值为零，第一次建增流网络求最短路径时，因无负权边，当然可以采用标号法进行计算。为了使以后建立增流网络时不出现负权边，采取的办法是将 G中有流边f(e)?0的权w(e)修正为0。为此， 每次在增流网络上求得最短路径
38
山东科技大学本科毕业设计（论文）
后，以下式计算G中新的边权w''(u,v):w''(u,v)?L(u)?L(v)?w(u,v)(*) 式中L(u),L(v) -- 计算G'的x至y最短路径时u和v的标号值。第一次求最短径时如果(u,v)是增流路径上的边， 则据最短 路径算法一定有
L(v)?L(u)?w'(u,v)?L(u)?w(u,v),
代入(*)式必有
w(u,v)?0.。
如果(u,v)不是增流路径上的边，则一定有：
L(v)?L(u)?w(u,v)，
代入(*)式则有 (u,v)。 可见第一次修正 w (e),后，对任一边，皆有w(e)?0，
?0。以后每次迭代计算若 且有流 的边（增流链上的边），一定有w(e）f(u,v)?0，增流网络需建立(v,u)边，边权数w'(u,v)??w(u,v)?0，即不
会再出现负权边。 此外，每次迭代计算用(*)式修正一切w(e)， 不难证明对每一条x至y的路径而言，其路径长度都同样增加L(x)?L(y)。因此，x至y的最短路径不会因对w(e)的修正而发生变化。
39