最大流的算法 Algorithm for Maximum Flow

算法名称

复杂度

概要

增广路方法

Augmenting path method (Ford Fulkerson method)

一般增广路算法

Labeling algorithm

O(nmU)

在残留网络中，每次任意找一条增广路径增广。

容量缩放增广路算法

Capacity scaling algorithm

O(nm logU)

在残留网络中，每次找一条有最大可增广容量和的增广路径增广，即残留网络中源到汇的最长路。

最短增广路算法

Shortest augmenting path

algorithm (Edmonds Karp

algorithm)

O(nm­­2­)

在残留网络中，每次找一条含结点数最少的增广路增广，即残留网络中源到汇的BFS 路径。

连续最短增广路算法

Successive shortest

augmenting path algorithm

(Dinic algorithm)

O(n­­2­m)

在 Edmonds Karp 的基础上改造。在每次BFS 找增广路时，记录每个点的距离标号。在距离标号的所构成的最短路图上，不断地 DFS找增广路。即一次标号多次增广，以提高速度。

预流推进方法

Preflow-push method

一般预流推进算法

Generic preflow-push

algorithm

O(n­­2­m)

维护一个预流，不断地对活跃结点执行push操作或relabel操作来调整这个预流，直到不能操作。

先进先出预流推进算法

FIFO preflow-push algorithm

O(n­­3­)

以先进先出队列维护活跃结点。

最高标号预流推进算法

Highest-label preflow-push

algorithm (Relabel-to-Front

algorithm)

O(n­­2­m­­1/2­)

每次检查具有最高标号的活跃结点。