Chapter 8. Maximum Flow
The maximum-flow problem is the problem of determining how much of some quantity (say, water) can move through a network.
There is a long history of algorithms for solving the maximum-flow problem, with the first algorithm due to Ford and Fulkerson [12]. The best general-purpose algorithm known to date is the push-relabel algorithm of Goldberg [9, 16, 17], which is based on the notion of a preflow introduced by Karzanov [20].
The BGL contains two algorithms for computing maximum flows. The Edmunds–Karp algorithm (a refinement of the original Ford–Fulkerson) and the push-relabel algorithm.
8.1 Definitions
A flow network is a directed graph G = (V, E) with a source vertex s and a sink vertex t. Each edge has a positive ...
Get The Boost Graph Library: User Guide and Reference Manual now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
