Network Flow

Compute the maximum amount of flow that can be sent through a network from a source to a sink, or the minimum-cost way to route a given amount of flow.

Max flow / min cut

Algorithm	Complexity	When to use
Push-Relabel	O(V³)	General-purpose max flow. Goldberg’s algorithm; fastest in practice for most graphs.
Edmonds-Karp	O(V · E²) or O(V · E · U) for integer capacities bounded by U	Augmenting-path based. Simpler to understand; generally slower than push-relabel for dense graphs.
Boykov-Kolmogorov	No tight worst-case bound; very fast in practice	Optimized for vision/segmentation graphs (grid-like structure with short augmenting paths). Reuses source/sink search trees across iterations.
Stoer-Wagner	O(V · E + V² log V)	Global minimum cut (no source/sink). Undirected graphs only.

Algorithm

Complexity

When to use

Push-Relabel

O(V³)

General-purpose max flow. Goldberg’s algorithm; fastest in practice for most graphs.

Edmonds-Karp

O(V · E²) or O(V · E · U) for integer capacities bounded by U

Augmenting-path based. Simpler to understand; generally slower than push-relabel for dense graphs.

Boykov-Kolmogorov

No tight worst-case bound; very fast in practice

Optimized for vision/segmentation graphs (grid-like structure with short augmenting paths). Reuses source/sink search trees across iterations.

Stoer-Wagner

O(V · E + V² log V)

Global minimum cut (no source/sink). Undirected graphs only.

Min-cost flow

Algorithm	When to use
Cycle Canceling	Simple min-cost flow. Slow but correct.
Successive Shortest Path	Min-cost flow with non-negative edge costs. Faster than cycle canceling.
Find Flow Cost	Computes the total cost of an existing flow solution.

Algorithm

When to use

Cycle Canceling

Simple min-cost flow. Slow but correct.

Successive Shortest Path

Min-cost flow with non-negative edge costs. Faster than cycle canceling.

Find Flow Cost

Computes the total cost of an existing flow solution.

Matching

Algorithm	When to use
Edmonds Matching	Maximum cardinality matching (most edges, ignoring weights).
Maximum Weighted Matching	Maximum weight matching (highest total edge weight).

Algorithm

When to use

Edmonds Matching

Maximum cardinality matching (most edges, ignoring weights).

Maximum Weighted Matching

Maximum weight matching (highest total edge weight).

For max flow, start with push-relabel. Use Boykov-Kolmogorov only for grid-like graphs (image segmentation). For minimum cut without a fixed source/sink, use Stoer-Wagner.

Setting up a flow network

All max-flow algorithms require internal property tags: edge_capacity_t, edge_residual_capacity_t, and edge_reverse_t. For every edge (u,v) you must also add a reverse edge (v,u) and link them via the reverse-edge map.

using Traits = adjacency_list_traits<vecS, vecS, directedS>;
using Graph = adjacency_list<vecS, vecS, directedS,
    no_property,
    property<edge_capacity_t, int,
    property<edge_residual_capacity_t, int,
    property<edge_reverse_t, Traits::edge_descriptor>>>>;

// Helper to add an edge and its reverse
void add_flow_edge(Graph& g, int u, int v, int cap) {
    auto e1 = add_edge(u, v, g).first;
    auto e2 = add_edge(v, u, g).first;
    put(edge_capacity, g, e1, cap);
    put(edge_capacity, g, e2, 0);    // reverse edge has 0 capacity
    put(edge_reverse, g, e1, e2);
    put(edge_reverse, g, e2, e1);
}

Boykov-Kolmogorov additionally requires vertex_color_t, vertex_distance_t, and vertex_predecessor_t internal properties on vertices. Push-Relabel and Edmonds-Karp do not.

Edit this Page