算法技术手册（原书第2 版）

网络流算法

｜

209

网络流算法

任何可行的流

f

经过网络时应满足以下准则。

容量限制

通过一条边的流量

f

(

u

,

v

)

不能为负，且不能超过边的容量

c

(

u

,

v

)

，即

0

≤

f

(

u

,

v

)

≤

c

(

u

,

v

)

。如果网络中不存在边

(

u

,

v

)

，则定义

c

(

u

,

v

)= 0

。

流量守恒

除了源顶点

s

和汇点

t

外，对于每个顶点

u

∈

V

，必须满足所有入流等于所有出流这

一准则，即所有边

(

v

,

u

)

∈

E

（流入

u

）上的流量

f

(

v

,

u

)

必须等于所有边

(

u

,

w

)

∈

E

（从

u

流出）上的流量之和。这确保了在网络中，除了源顶点和汇点之外，不存在凭空

产生流或者某个流不被消费的情况。

反对称性

f

(

v

,

u

)

的数量与从顶点

u

到

v

的网络流刚好相反。也就是说，

f

(

u

,

v

)

必须等于

－

f

(

v

,

u

)

。

在接下来的算法中，我们提到的网络路径指的都是一条没有环的路径，它由不同的顶点

<

v

1

，

v

2

,

…

,

v

n

>

所连接的

(

v

i

,

v

j

)

共

n

－

1

条边构成。在图

8-2

所示的流网络中，

<

v

3

，

v

5

,

v

2

,

v

4

>

是可能的一条网络路径。网络路径会忽略边的方向，这对于正确构造增广路径是

有必要的，在接下去的算法中我们将会看到这点。图

8-2

中另一条可能的网络路径是

<

s

,

v

1

,

v

4

,

v

2

,

v

5

,

t

>

。

8.2 最大流

在一个流网络中，如果给定了边集

E

中所有有向边

e

= (

u

,

v

)

的容量限制

c

(

u

,

v

)

≥

0

，我

们可以计算出顶点

s

和

t

之间的最大流。也就是说，在每条边都有容量限制的情况下，

从源顶点

s

输出的，通过这个网络达到汇点

t

的最大流量是可以计算出来的。从一个可 ...