CoreSource checked

Ford-Fulkerson

Computes maximum flow by repeatedly augmenting along residual paths.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Advanced
Family: Network Flow
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 2
Relationships: 6
Code example: Ready
Visualization: Ready

Overview

Ford-Fulkerson maintains a residual network and sends additional flow through any available source-to-sink path until no augmenting path remains.

Core Concepts

residual graphaugmenting pathcapacity constraintflow conservation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E)

Average

O(E * max_flow)

Worst

O(E * max_flow)

Space

O(V + E)

When to Use

Use it to explain residual networks and augmenting paths.
Use it when capacities are integral and the instance is small.
Use a specified path rule when a runtime guarantee is needed.

When Not to Use

Avoid arbitrary path choices with irrational capacities.
Avoid it on large networks without a stronger path-selection rule.
Avoid omitting reverse edges in the residual graph.

What It Does

Computes maximum flow by repeated augmentation
Maintains residual capacities

Use Cases

Teaching maximum-flow fundamentals
Small integral-capacity networks
Basis for Edmonds-Karp and related variants

Inputs

Graph
Start nodes or query nodes
Traversal state

Outputs

Visited nodes
Derived graph relationships

Key Formulas (2)

Residual capacity

residual(u, v) = capacity(u, v) − flow(u, v)

residual(u, v) = capacity(u, v) - flow(u, v)

Shows how much additional flow can still be sent along an edge.

Augmenting amount

δ = min residual(u, v) over path

delta = min residual(u, v) over path

Limits a path augmentation by its bottleneck residual capacity.

Pseudocode

1.Prepare the inputs and state needed for Ford-Fulkerson.
2.Apply the residual graph step while the stopping condition has not been met.
3.Update intermediate state and discard invalid candidates.
4.Return visited nodes.

Canonical Example

Input: s->a->t with capacities 3 and 2
Output: flow = 2 on that path
Explanation: The bottleneck edge limits the augmenting path to 2 units of flow.

Implementation Notes

Find any s-t path in the residual graph.
Augment by the minimum residual capacity on that path.
Update both forward and reverse residual capacities.

Common Pitfalls

Forgetting reverse residual capacity.
Assuming every path-selection strategy has the same runtime.
Using floating capacities without convergence care.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Highlight active nodes, discovered edges, and the graph structure produced by each step.

Step 1 of 4: Prepare the inputs and state needed for Ford-Fulkerson.

graph-traversal-mechanism

Notes

Ford-Fulkerson operates in O(E * max_flow) time and O(V + E) space within the Network Flow family. Key governing relation: residual(u, v) = capacity(u, v) - flow(u, v). Often compared with Edmonds-Karp and Dinic's Algorithm.