Graphics Reference
In-Depth Information
bottleneck—the minimum cut surface. It turns out that the maximum flow
problem is convex and is consequently easier to solve than the dual problem
of finding the minimum cut.
Augmenting Path Algorithm
The best known algorithm for solving the maximum flow problem is the fa-
mous Ford-Fulkerson [63] augmenting path algorithm. This algorithm suc-
cessively increases the maximum flow from source s to sink t by continually
locating paths along which more flow may be pushed. Once all paths from
source to sink are saturated, the flow is maximal. The pseudocode for the
Ford-Fulkerson algorithm is given in Figure 10.15.
Ford Fulkerson Augmenting Path Algorithm
Initialization:
Set F = 0 on each edge
Main loop:
- Search for an s-t path along which more flow may be pushed
- Ifnosuchpathexists,halt
- Otherwise, increase the flow uniformly along this path until at least one edge
becomes saturated
Fig. 10.15. Pseudocode for Ford-Fulkerson Augmenting Path algorithm (from [7]).
Preflow Push Algorithm
An alternative to the augmenting path algorithm is the more recent preflow
push algorithm of Goldberg and Tarjan [67]. One advantage of this formulation
is that it is highly parallelizable compared to the Ford-Fulkerson algorithm.
A preflow is like a flow, except that the total amount flowing into a vertex is
allowed to exceed the total amount flowing out. The algorithm maintains a
preflow in the original network and then pushes excess local flow toward the
sink along what are estimated to be shortest paths.
A vertex that has greater inward flow than outward flow is called an active
vertex—the excess being the positive difference between the two. The algo-
rithm repeatedly pushes flow outwards from active vertices toward the sink.
A height function H is introduced on the vertices to guide the flow along
the shortest unsaturated path toward the sink. The source and sink have
fixed heights of
and 0, respectively, and may never become active. Active
vertices are stored in a queue, Q . The pseudocode for the Goldberg-Tarjan
algorithm is given in Figure 10.16.
|
V
|
Search WWH ::




Custom Search