第三节 流的计算

地理系统中的流，泛言之，就是指目标从一个地点向另一个地点转移的运动过程。譬如，将原料从产地运往加工厂，将产品由加工厂运往销售地， 将人或货物从一个地点运向另一个地点，河水由一个汇流点流向另一个汇流点，等等，都可以认为是流。虽然，地理系统中的流可以有不同的形式，但我们所关心的是各种流的共性问题，例如，我们希望从一个地点经由运输系统到达另一个地点的运输量达到最大，或者从一个地点经由运输系统将一定数量的目标送至另一地点所需的费用达到最小。

一、有关概念及流的增值算法

地理系统中各种形式的流，均可被描述为网络图中的流，即从一个顶点沿着赋权有向图的边（或称弧)，将目标移送至另一个顶点的一条路径。目标开始其行程的顶点称为发点，记为 S；目标终止其行程的顶点称为收点，记为 t。从发点流向收点的目标称为单位流量或单位。如上所述，单位流量可以是原料、产品、其它货物或者人，也可以是其它物质、能量或信息。

如果通过边（u，v)的单位流量是有限制的，则称边（u，v)为有容量的边。我们用 m（u，v)表示边（u，v)的最大容量，用 c（u，v)表示通过边 e=

（u，v)移运一个单位的费用。例如，一支由 12 辆军用卡车组成的战时车队必须从军需工厂（发点)运输军需用品至部队所在地（收点)。联结军需工厂与部队所在地的公路可以用图表示，图的边对应于未防护的公路，顶点对应于公路汇合点。为了安全上的理由，经过每条边的卡车数量有一个限制（边的容量)。根据以往的经验，调度员可以知道卡车在每一个公路区段上费用（边的费用)。求 12 辆军用卡车中每一辆的最佳路线，就是对应的公路网络中，

在不超过边的容量的条件下，从出发点向收点运输 12 个单位流量的费用达到最小。

设给定一个图，其中有一定数量的单位由发点运至收点，而且每个单位所采取的路线也为已知。通过边（u，v)的单位的数量称为边（u，v)的流， 用 f（u，v)表示。显然，0≤f（u，v)≤m（u，v)。图中的边可以分为三类：

1) N，流不能有任何增加或减少的边集合； 2)I，流可以增加的边集合； 3)R，流可以减少的边集合。

例如，具有零容量或过高通行费用的边属于集合 N；具有未使用容量的边属于集合 I；已有流的边属于集合 R。集合 I 中的边称为可增加的边；集合R 中的边称为可减少的边；显然，每一条边必然至少属于这三种集合 N，I，R 之一。一条边还可能同时属于两种集合 I 和 R，当每一条边已经运送单位流量，但是可以有增加或减少的流时，就可以产生这种情况。这样的边称为中间边。

令 i（u，v)表示边（u，v)中的流可以增加的最大量，r（u，v)表示边

（u，v)中的流可以减少的最大量。于是，i（u，v)=m（u，v)-f（u，v)；r

（u，v)=f（u，v)。

设我们欲从 s 再运送某些单位至 t，有几种方法可以完成这一任务（当然，前提是从 s 可以运送更多的单位至 t)。首先，如果能够找出一条从 s 至t 的路 p，而且这条路全部由可增加的边组成，则从 s 沿着路 p 就可以再运送追加的流至 t（见图 7-8)。从 s 沿着路 p 可以运送多少追加的单位流量至 t

呢？因为 i（u，v)表示边（u，v)中的流可以增加的最大量，

所以至多可以有

min

( u ,v )∈P

｛i（u，v）｝追加的单位流量从s运送至t。对图

7-8 中的路 p，从 s 至 t 可以运送一个追加的单位流量，因为：

min｛i（s，a)，i（a，b)，i（b，t)｝=min｛3，2，1｝=1。

其次，如果我们能够找到一条从 t 到 s 的路 p，而这条路全部由可以减少的边组成，则这条路中每条边中的流可以减少，形成从 t 到 s 的较少的流， 因而就形成了从 s 到 t 的较大的净流（见图 7-9)。这条路中可以减少的流的最大量是多少呢？由于每条边（u，v)最多可以有减少的流 r（u，v)，

所以路p中可以减少的最大流为

min ｛r（u，v）｝。对于图7 - 9中的路，

( u,v)∈P

从 t 到 s 可以取消一个单位流量，因为 min｛r（t，b)，r（b，a)，r（a， s)｝=｛1，2，1｝=1。能否找到另一种方法来增加从 s 到 t 的净流呢？这是可能的。将上述两种方法加以合并，我们可以找到一条从 s 至 t 的链，这条链具有以下性质：

（1)从 s 到 t 方向的边称为前向边，它们属于集合 I；

（2)从 t 到 s 方向的边称为后向边，它们都可以属于集合 R。

例如，考虑图 7-10 中从 s 至 t 的链 C。前向边为（s，a)，（a，b)和（d， t)；后向边为（c，b)和（d，c)。如果每条前向边都属于 I，并且每条后向边都属于 R，则沿着可增加的前向边前进，沿着可减少的后向边倒退，这样， 从 s 沿着链 C 就可以运送追加的流至 t。从 s 沿着这样一条链至 t 可以运送的追加的流的最大量是下列两个数的最小值：

min｛i（u，v)∶（u，v)为前向边｝ min｛r（u，v)∶（u，v)为后向边｝

这两个数的最小值称为链 C 的最大流的增值。在图 7-10 中，前向边的可以增加的流的最大量为 min｛i（s，a)，i（a，b)，i（d，t)｝=min｛4，3， 3｝=3；后向边的流的可以减少的最大量为 min｛r（d，c)，r（c，b)｝=min

｛5，2｝=2。所以沿着这条链从 s 至 t 可以再运送 2 个追加的单位流量。 从 s 至 t 有任一条链（如上面所讨论的三种不同形式那样)，沿着这条链

可以运送追加的单位流量，这样的链称为流的增值链。我们怎样确定从 s 至t 是否存在一条流的增值链呢？应用下列算法，即所谓流的增值算法很容易解决这一问题，这种算法的基本思路是，从发点 s 生长出一棵由已着色的边组成的树，追加的单位流量可以沿着这些边从 s 运出。将边按上述分类方法分为集合 R，I，N，从 s 至 t 已着色的树中唯一链就是从 s 至 t 的流的增值链时，算法对收点 t 着色；从 s 至 t 不存在流的增值链时，算法不对收点 t 着色。流的增值算法的步骤是：

第一步：确定哪些边属于集合 N、I 和 R。因为在集合 N 中的边、流不能改变，所以这些边可以忽略，不予考虑。对顶点 s 着色。

第二步：按照下列规则，对边和顶点着色，直至顶点 t 已被着色或不可能再进行着色为止。

如果顶点 u 已着色，而顶点 v 尚未着色，则在下列情形之一时，可对顶点 v 和边（u，v)着色：

（1)如果边（u，v)∈I，则可对顶点 v 和边（u，v)着色。

（2)如果边（u，v)∈R，则对顶点 v 和边（u，v)着色。

如果顶点 t 已被着色，则从 s 至 t 存在一条由已着色边组成的唯一链。这条链就是流的增值链。如果在算法终止以后，t 仍未被着色，则从 s 至 t 不存在流的增值链。

例：应用流的增值算法，找出图 7-11 中从 s 至 t 的一条流的增值链。每条边旁的字母表示这条边是可增加（可减少或者不变)的边。

开始对顶点 s 着色。从顶点 s，可对顶点 a 和边（s，a)着色，因为（s， a)∈I。从顶点 s，不能对顶点 c 和边（s，

c）着色，因为（s，c） ∉ I。这样就完成了从顶点s向外的着色。然后， 考虑从顶点a向外的着色。因（a， b） ∉I，故不能对顶点b和边（a， b)着色。（a，c)∈I，故可对顶点 c 和边（a，c)着色。又（d，a)

∉ R，故对顶点d和边（d， a）不能着色。这样就完成了从顶点a向外的

着色。同理，考虑顶点 c 向外的着色可对 d 和（c，d)及 b 和（b，c)着色。

我们再考虑从顶点 b 向外的着色。顶点 a、c、d 已经着色，所以不予考虑。（b，t)∈I，故顶点 t 和边（b，t)可以着色。此时，因为 t 已着色，所以算停止。已着色的边和顶点如图 7-12 所示。从 s 至 t 的流的增值链为：（s， a)、（a，c)、（b，c)、（b，t)，最大流的增值为 min｛i（s，a)，i（a， c)，r（b，c)，i（b，t)｝=min｛4，3，2，2｝=2。前向边（s，a)，（a， c)，（b，t)可以增加流 2 个单位；后向边（b，c)可以减少流 2 个单位。这意味着以前经过（b，c)的两个单

位流量应改变路线而沿着（b，t)行进，在顶点 c 处，则由 s 点经过（s， a)和（a，c)到达的追加的两个单位流量来代替。

二、最大流的计算

最大流问题，就是在一个有容量的图中从发点到收点找出一条可以运送最大数量单位流量的途径，而且不得超过边的容量。例如，有一旅行代办人必须为某天由 s 机场至 t 机场的 10 名游客的飞行作出安排。在那天，s 机场至 t 机场的直达航线只有 7 个座席，而 s 机场至 a 机场的航线有 5 个座席，a 机场至 t 机场的航线有 4 个座席。那么该旅行代办人应该怎样安排？这一问题可以被描述为最大流的问题。首先可构造一个网络图，其中每一条边表示一条航线，这样共有三条边（s，t)，（s，a)，（a，t)。对每条边指定一个容量，这个容量代表每条边所表示的航线上的坐席数，即 m（s，t)=7，m（s， a)=5，m（a，t)=4。如果这个网络容许 10 个或 10 个以上单位的流从 s 点（发点)至 t 点（收点)而不超过任一条边的容量，则旅行代办人在选定日期内可将全部游客送走。

如前所述，流就是从 s（发点)至 t（收点)的任何一种运送。如果令 f（u， v)表示经由边（u，v)运送的单位数量，则对从 s 至 t 的任何一个流它都具有以下几个性质：

（1)从每一个顶点 u（u≠s，u≠t)出去的单位数量一定等于到达该顶点的单位数量，即

Σf（u，v)-Σf（v，u)=0 （1)

v∈V v∈V

（1)式中，V 表示网络图中所有顶点组成的集合。

（2)经由边（u，v)运送的流的单位数量一定不能大于该边的容量，即0≤f（u，v)≤m（u，v)（（u，v)∈E) （2)

（2)式中，E 为网络图中所有边组成的集合。

（3)从发点出去的单位流量的净数 Q 一定等于到达收点的单位流量的净数，即Σ

f（s，v)-Σf（v，s)=Q （3)

v∈V v∈V

Σf（v，t)-Σf（t，v)=Q （4)

v∈V v∈V

从 s 至 t 的每一个流都必须满足上述四个条件（1)—（4)，而且，如果可以找到一个满足上述四个条件的数值 f（u，v)［（u，v)∈E］的集合，则这些数值就对应于一个从 s 至 t 的流。因此，对于（u，v)∈E，数值 f（u， v)的集合是一个流的充要条件是关系式（1)—（4)成立。

最大流问题就是求 Q 的最大值，它必须受关系式（1)—（4)条件的约束。显然，这是一个线性规划问题，可以单纯形方法求解。但是，福特和富尔克逊（Ford，Fulkerson)于 1962 年提出了一个更好的、更直观的求解方法，即最大流的算法。这个算法的思路十分简单：从 s 至 t 的任何一个流开始，用流的增值算法寻找流的增值链。如果找出一条从 s 至 t 的流的增值链，则沿着这条链运送尽可能多的单位流量。然后，再开始寻找另一条流的增值链，⋯⋯。如果再找不出流的增值链，则算法停止，因为现有的从 s 至 t 的流已是从 s 至 t 的最大流。根据这一思路，我们可以将最大流的算法步骤描述如下：

第一步：令 s 表示发点，t 表示收点。选择任一个从 s 至 t 的起始流， 亦即，选择满足关系式（1)—（4)的 f（u，v)数值的任一个集合，如果不知道这样的流，则对所有（u，v)∈E，用 f（u，v)=0 作为起始流。

第二步：如果 f（u，v)＜m（u，v)，令 i（u，v)=m（u，v)-f（u，v)，

（u，v)∈I；如果 f（u，v)＞0，令 r（u，v)=f（u，v)，（u，v)∈R。

第三步：对第二步中定义的集合 I 和 R，执行流的增值算法。如果应用流的增值算法未发现流的增值链，则算法停止，现有的流就是最大流。否则， 沿着流的增值算法所发现的流的增值链，作出最大可能流的增值，再返回第二步。

例：在图 7-13 中，每条边旁的数表示边的容量，即 m（u，v)。试求从 s 至 t 的最大流。

第一步：算法由零流开始，即对所有的边（u，v)∈E，令 f（u，v)=0。第二步：因为对所有的边（u，v)∈E，f（u，v)＜m（u，v)，所以每条

边都是集合 I 的一个元素，令 i（u，v)=m（u，v)-f（u，v)=m（u，v)。因为对所有的边（u，v)∈E，f（u，v)=0，所以没有边属于 R。

第三步：现在，用流的增值算法寻找一条从 s 至 t 的流的增值链。显然， 可以看出，从 s 至 t 有几条流的增值链。假设产生一条流的增值链为（s，a)，

（a，b)，（b，t)，沿着这条链的最大流的增值是 min｛i（s，a)，i（a， b)，i（b，t)｝=min｛2，3，2｝=2。因而，在这条链中，将每一条边增加两个单位，即 f（s，a)=2+0=2，f（a，b)=2+0=2，f（s，b)=0，f（b，t)=2+0=2， f（a，c)=0，f（c，t)=0。以下返回第二步。

第二步：对于上面新产生的流，

f（ s， a） = 2 = m（ s， a），（s，a）

（s，a)=2。

∉I；（ s， a）∈R， r

f（a，b)=2＜m（a，b)，（a，b)∈I， i（a，b)=m（a，b)-f（a，b)=3-2=1；

（a，b)∈R，r（a，b)=2。

f（b，t)=2=m（b，t)， （b，t)∈I； （b，t)∈R，r（b，t)=2。f（s，b)=0＜m（s，b)，（s，b)∈I， i（s，b)=m（s，b)-f（s，b)=3-0=3；

（s，b)∈R。

f（a，c)=0＜m（a，c)，（a，c)∈I，i（a，c)=m（a，

c） - f（a，c） = 4 - 0 = 4；（a，c） ∉R。

f（c，t)=0＜m（c，t)，（c，t)∈I， i（c，t)

=m （c，t） - f（c，t） = 1 - 0 = 1； （c，t） ∉R。

第三步：再次用流的增值算法寻找另一条流的增值链。算法将产生唯一的流的增值链为（s，b)，（a，b)，（a，c)，（c，t)。沿着这条链的最大可能流的增值是 min｛i（s，b)，r（a，b)，i（a，c)，i（c，t)｝=min｛3， 2，4，1｝=1。因此，有一个追加的单位流量沿着这条链从 s 运送至 t。这条链的每一条前向边（s，b)，（a，c)，（c，t)的流增加一个单位，其后向边

（a，b)的流减少一个单位，最终得到的流是：f（s，a)=2，f（a，b)=1，f

（b，t)=2， f s ，b)=1，f（a，c)=1，f（c，t)=1。现在，单位流量通过下列路径：

1 个单位从 s 经由边（s，a)，（a，b)，（b，t)至 t。

1 个单位从 s 经由边（s，b)，（b，t)至 t。

1 个单位从 s 经由边（s，a)，（a，b)，（b，t)至 t。以下返回第二步。第二步：对上面产生的流，

f（ s， a）

（s，a)=2。

= 2 = m（ s， a），（s， a）

∉ I；（ s， a）∈ R， r

f（a，b)=1＜m（a，b)，（a，b)∈I，i（s，a)=m（a，b)-f（a，b)=3-1=2；

（a，b)∈R，r（a，b)=1。

f（ b， t）

r（b，t)=2。

= 2 = m（ b， t）， （ b， t）

∉ I； （ b， t）∈R，

f（s，b)=1＜m（s，b)，（s，b)∈I， i（s，b)=m（s，b)-f（s，b)=3-1=2；

（s，b)∈R，r（s，b)=1。f（a，c)=1＜m（a，c)，（a，c)∈I，i（a，c)=m（a，c)-f（a，c)=4-1=3；

（a，c)∈R，r（a，c)=1。

f（ c， t）

r（c，t)=1。

= 1 = m（ c， t），（ c， t）

∉ I；（ c， t）

∉ R，

应用流的增值算法，将以上的流作为起始流，我们再也不能找到追加的流的增值链［流的增值算法可以对顶点 s，b，a，c（按此顺序)着色，但不能对顶点 t 着色］。所以，最大流算法终止。终止流（如上所述)就是最大流。在算法终止后，由几条边构成的一个已着色端点和一个未着色端点的截是

（b，t)，（c，t)，这个截的容量是 m（b，t)+m（c，t)=2+1=3，这就是由最大流算法得到的从 s 运送至 t 的单位数量。

三、最小费用流的算法

在一个有容量的图中，通过每一条边运送一个单位时，都有一个费用， 最小费用流问题，就是考虑怎样从发点至收点以最小费用运送一个给定数量Q 的单位流量。例如，一个制造商欲将成品从工厂运至仓库，他可以从许多条运输路线中进行选择。在不同的路线上，单位重量成品的运输费用是不同的。每条路线只能担负有限总重量的货物运输。制造商欲将全部成品从工厂运至仓库，用什么方法使运费达到最小？如果用顶点 s 表示工厂，用另一个顶点 t 表示仓库，两条或两条以上路线的每一个交汇点都用一个顶点表示； 令每条边的容量等于相应的一段路线所能担负的货物运输的最大重量，并且令每条边的费用等于通过该边所对应的一段路线的单位重量的运费，则制造商的问题就是在这个图上求从 s 至 t 的最小费用流问题。

令 c（u，v)表示沿着边（u，v)运送一个单位流量的费用。首先，我们假设 c（u，v)都是正整数（后面再对这一假设进行修正)。如前所述，令 f

（u，v)表示通过边（u，v)的流的单位数量。当然 f（u，v)≥0。令 Q 表示从发点运送至收点的单位数量。则最小费用流问题可以表示为，

 

min ∑c（u，v）f（u，v）

（5）

( u ,v ) 

满足约束条件：

∑［f（s，v） - f（u，s）］ = Q

v

（6）

∑［f（u，v） - f（v，u）］ = 0（u≠s，u≠t） （7）

v

∑［f（t，u） - f（v，t）］ = -Q

v

（8）

0≤f（u，v）≤m（u，v）［对所有的（u，v）∈E］ （9）

显然，最小费用流问题也是一个线性规划问题（实际上，最大流问题可视为最小费用流问题。其中所有各条边的费用为零，并且 Q 为最大可能流的数值)。

令（5)式由下式代替：

max｛PQ - ∑（u，v）f（u，v）｝ （10）

(u, v)

（10)式中，P 是任一个大数，例如，大于从 s 至 t 运送一个单位的最大总费用的数。如果将 P 解释为从 s 至 t 运送一个单位所得的利润，则（10)式可解释为扣除运费以后的最大可能净利润。因而，按照这一解释，使（10)式最大的任一个流也将使（5)式最小，反之亦然。

最小费用流的算法，首先从 s 至 t 运送尽可能多的全程每单位总费用为零的单位。其次，最小费用流算法从 s 至 t 运送尽可能多的全程每单位总增加费用为 1 的单位，⋯⋯。当总数为 Q 的单位已从 s 运送至 t 时，或者，当从 s 至 t 没有更多的单位可以运送时，算法终止。换句话说，算法首先对 P=0 解（6)—（10)的问题，其次对 P=1 解题，再次对 P=2，⋯⋯。

设算法已从 s 至 t 运送尽可能多的总增加费用为 P-1 或稍少的单位。算法怎样确定从 s 至 t 运送每单位总增加费用为 P 的单位流量呢？为做到这一步，算法必须找出一条从 s 至 t 的增值链，这条链具有这样的性质：“沿着这条链”运送一个单位，总的增加费用等于 P。为了有助于明了这一思路， 考虑图 7-14。在这个图中，从 s 至 t 运送一个单位流量的费用最小的路线是

沿着路（s，a)，（a，b)，（b，t)进行。单位流量所担负的总费用为 2+1+2=5， 如果 Q=1，就构成了一个最小费用流。

假设 Q=2，根据检查结果，剩下仅有的增值链为（s，b)，（a，b)，（a， t)，这条链可以担负运送从 s 至 t 的一个追加单位。如果第二个单位流量从 s 出发，则第一个单位流量将在顶点 a 处改变方向，取路（s，a)，（a，t)。第二个单位流量将在顶点 b 处代替第一个单位流量，取路（s，b)，（b，t)。这两个单位流量的总费用为 c（s，a)+ c（a，t)+c（s，b)+ c（b，t)= 2+4+4+2=12，比原先的费用增加了 7。所增加的 7 是从流的增值链（s，b)，（a，b)，（a， t)中按下列方式形成的：

在前进方向，通过边（s，b)，形成+4 的费用； 在后退方向，通过边（a，b)，形成-1 的费用； 在前进方向，通过边（a，t)，形成+4 的费用。

因此，算法必然要找出一条流的增值链，这条链具有这样的性质：链的前向边费用之和减去后向边费用之和等于 P。

要完成这项计算，须对图中每一个顶点 u 指定一个整数 P（u)，这些顶点数值 P（u)具有这样的性质：P（s)=0，P（t)=P，对所有各顶点 u≠s，u

≠t，0≤P（u)≤P。算法仅沿着边（u，v)改变流量，对于边（u，v)，有

P（v)-P（u)=c（u，v)（11)

如果算法找出一条从 s 至 t，由所有满足方程（11)的边组成的流的增值链，则从 s 沿着这条链运送至 t 的每个单位的总增加费用等于 P。以此为依据，最小费用流的算法步骤如下：第一步（开始)：首先令每条边（u，v)中的流 f（u，v)=0，对所有各顶点 u，令 P（u)=0。第二步（决定哪些边可以改变流量)：令 I 为满足条件：

P（v)-P（u)=c（u，v)

及 f（u，v)＜m（u，v)

的所有边组成的集合。令 R 为满足条件：

的所有边组成的集合。

P（v)-P（u)=c（u，v)及 0＜f（u，v)

令 N 为集合 E-IUR（I 与 R 中的那些边仅为可以考虑改变流量的那些边。因而，只能在满足方程（11)的边上改变流量)。

第三步（改变流量)：按上述第二步定义的 I，R 和 N，执行最大流算法。当从 s 已经运送总数为 Q 的单位流量至 t 时，或者，对 I、R、N 集合的现有组成部分来说，当从 s 至 t 已不可能再运送更多的流时，算法停止。如果先发生前一种情况，因为最终流就是从 s 运送 Q 单位至 t 的最小费用流，所以算法停止。如果先发生后一种情况，检查一下，现有的流是否为从 s 至 t 的最大流（检查方法：验证用流的增值算法最后着色所产生的截是否已经饱和)。如果就是最大流，因为从 s 至 t 已不能再运送更多的单位流量，并且最终流就是最小费用流，所以算法停止，如果不是最大流，则转向第四步。

第四步（改变顶点数值)：考虑流的增值算法所作的最后着色（流的增值算法是最大流算法中的一个子程序，而最大流算法又是最小费用流算法的一

个子程序)。将每一个未着色顶点 u 的顶点数值 P（u)增加+1（注意，t 尚未着色，否则就已发现一条流的增值链，所以对 P（t)增加+1)。返回第二步。例：在图 7-15 中，每条边（u，v)旁边的第一个数字表示边的费用 c（u，

v)，第二个数字表示边的容量 m（u，v)。试用最小费用流算法找出最小费用流。

开始时，所有顶点数值都是零，并且所有顶点除发点外都未着色，发点s 总是已着色的。迭代计算的结果分别列表如下（见表 7-2)。

从表 7-2 知道，顶点 t 已经着色。从 s 至 t 沿着路（s，a)，（a，b)，

（b，t)可以运送 2 个单位流量。因此，f（s，a)=2，f（a，b)=2，f（b，t)=2。继续迭代，计算结果列于表 7-3。

从表 7-3 可以看出，顶点 t 已经着色。从 s 至 t 沿着链（s，b)，（a， b)，（a，t)可以运送 1 个单位流量。因此，f（s，a)=2， f（s，b)=1，f

（a，b)=1， f（a，t)=1，f（b，t)=2，继续迭代，计算结果见表 7-4。因为从已经着色顶点至未着色顶点的边［边（s，a)，（s，b)］已经饱

和，所以从 s 至 t 不能再