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

208

｜

第

8

章

在本章中，我们将阐述

Ford-Fulkerson

算法。该算法用于解最大流问题。

Ford-

Fulkerson

算法也可以直接用于二分图匹配问题，如图

8-1

所示。此外，一旦理解了

Ford-Fulkerson

算法的基本原理，就不难发现，该算法框架可以用于解决最小费用流问

题，例如转运问题、运输问题以及任务分配问题。

从理论上来说，线性规划（

LP

）也可以用于解决图

8-1

中的所有问题，但是必须得先将

这些问题转换成正确的线性表示形式，并将得到的解转换成原有的形式（我们将在本章

末尾介绍这个转换过程）。线性规划用于在包含线性关系的数学模型中求解最优解（例

如最大利润和最小费用）。不过在实际使用中，对于图

8-1

中的问题，本章所描述的算

法性能要比线性规划高上好几个数量级。

8.1 网络流

流网络可以抽象为一个有向图

G

= (

V

,

E

)

，其中

V

是顶点集，

E

是连接这些顶点的边集。

图是连通的（虽然并不是每条边都需要展示出来）。有一个特殊的源顶点

s

（

s

∈

V

），它

负责生产商品，然后通过图的边运输到汇点

t

∈

V

（也称为终点或者目标点）进行消费。

流网络假设源顶点能够生产无限多的商品，并且汇点能够消费完所有接收到的商品。

每条边

(

u

,

v

)

都有一个流量

f

(

u

,

v

)

，表示从

u

运输到

v

的商品单位数目。同样，每条边也

有一个容量

c

(

u

,

v

)

，表示能够从

u

运输到

v

的最多商品的单元数量。在图

8-2

中，对源

顶点

s

和汇点

t

之间的每个顶点都进行了编号，并且每条边也使用诸如

f/c

的形式进行标

记，它们分别表示一条边上的流量以及最大允许的容量。例如边 ...