Core Concepts
Network flow theory addresses problems involving the movement of resources through a pipeline or transportation system modeled as a graph.
Common Problem Types
- Maximum Flow
- Minimum Cost Flow
- Multi-commodity Flow
- Circulation with Demands
This article focuses on the Maximum Flow problem, often visualized as finding the highest possible freight volume between two junctions in a railway network.
Augmenting Paths
An augmenting path is a route from the source (origin) to the sink (destination). The capacity of this path is determined by its bottleneck—the edge with the smallest remaining capacity along the route.
Modeling the Network
Directed Graphs
To solve these problems mathematically, we model the physical system as a directed graph (digraph).
- Vertices (Nodes): Represent locations like stations or junctions.
- Edges (Arcs): Represent routes like tracks or pipes. Since resources flow in a specific direction, these connection are vectors.
Capacity Constraints
Every edge $u \rightarrow v$ has a capacity $c(u, v)$, which defines the maximum volume that can pass through that specific route.
Flow Definition
Flow $f(u, v)$ is the actual amount of resource moving through an edge. It must satisfy two main rules:
- Capacity Constraint: $0 \le f(u, v) \le c(u, v)$.
- Flow Conservation: For any node (except source/sink), the total incoming flow equals the total outgoing flow.
The Challenge of Order
Consider a manual calculation where we try to push flow through paths greedily.
Scenario A (Correct Order):
- Path $S \to A \to D$: Flow 8 (limited by Source S).
- Path $S \to B \to C \to D$: Flow 3 (min of remaining capacities: 3, 10, 4).
- Path $S \to B \to E \to F$: Flow 3 (min of 3, 7, 5).
Total: 14.
Scenario B (Computer Randomness): If a computer processes paths in an arbitrary order, it might saturate a path inefficiently.
- Path $S \to B \to F \to G$: Flow 4.
- Path $S \to B \to C \to H$: Flow 2 (remaining capacity of B is now 2).
- Path $S \to A \to D \to G$: Flow 0 (G is full due to step 1).
- Path $S \to A \to E \to H$: Flow 2.
Total: 8 (Incorrect).
This demonstrates that greedy approaches fail without a mechanism to correct suboptimal choices.
The Solution: Reverse Edges
The Ford-Fulkerson method introduces reverse edges to allow algorithms to "undo" or redistribute flow.
When flow is sent along a path, we reduce the capacity of the forward edges and increase the capacity of reverse edges.
Redo Scenario B with Reverse Edges:
- $S \to B \to F \to G$: Send 4. (Add reverse capacity $G \to F$ of 4).
- $S \to B \to C \to H$: Send 2.
- $S \to A \to D \to G$: Send 0 (G is full).
- New Path Found: $S \to A \to D \to \text{Rev}(G \to F) \to \text{Rev}(F \to B) \to C \to H$.
- This effectively moves 2 units of the previous flow from $B \to F \to G$ to $B \to C \to H$, freeing up space.
- $S \to A \to E \to H$: Send 2.
Total: $4 + 2 + 2 + 2 = 10$ (Correct).
Concept: Reallocation
Instead of viewing reverse edges as "regret," view them as a reallocation mechanism. If Node A uses a route that blocks Node B, the reverse edge allows Node B to "borrow" capacity from A's allocated route, ensuring the total flow is maximized without blocking.
Algorithm Implementations
1. Ford-Fulkerson Method (DFS)
This method uses Depth-First Search to find augmenting paths repeatedly until no more exist.
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
const int INF = 1e9;
struct Arc {
int to, capacity, revIdx;
};
vector<Arc> graph[MAXN];
bool visited[MAXN];
void connect(int u, int v, int cap) {
graph[u].push_back({v, cap, (int)graph[v].size()});
graph[v].push_back({u, 0, (int)graph[u].size() - 1});
}
int depthFirst(int node, int sink, int flow) {
if (node == sink) return flow;
visited[node] = true;
for (auto& e : graph[node]) {
if (e.capacity > 0 && !visited[e.to]) {
int pushed = depthFirst(e.to, sink, min(flow, e.capacity));
if (pushed > 0) {
e.capacity -= pushed;
graph[e.to][e.revIdx].capacity += pushed;
return pushed;
}
}
}
return 0;
}
int fordFulkerson(int src, int sink) {
int totalFlow = 0;
while (true) {
memset(visited, 0, sizeof(visited));
int aug = depthFirst(src, sink, INF);
if (aug == 0) break;
totalFlow += aug;
}
return totalFlow;
}
int main() {
int edges, nodes;
while (cin >> edges >> nodes) {
for (int i = 1; i <= nodes; i++) graph[i].clear();
for (int i = 0; i < edges; i++) {
int u, v, w;
cin >> u >> v >> w;
connect(u, v, w);
}
cout << fordFulkerson(1, nodes) << endl;
}
return 0;
}
2. Edmonds-Karp Algorithm (BFS)
Edmonds-Karp optimizes Ford-Fulkerson by using Breadth-First Search to always find the shortest augmenting path, ensuring polynomial time complexity $O(VE^2)$.
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 210;
const int INF = 1e9;
int grid[MAXN][MAXN];
int parent[MAXN], limit[MAXN];
int nodes, connections;
int bfsSearch(int src, int sink) {
memset(parent, -1, sizeof(parent));
queue<int> q;
q.push(src);
limit[src] = INF;
while (!q.empty()) {
int cur = q.front(); q.pop();
for (int nxt = 1; nxt <= nodes; nxt++) {
if (grid[cur][nxt] > 0 && parent[nxt] == -1) {
parent[nxt] = cur;
limit[nxt] = min(limit[cur], grid[cur][nxt]);
if (nxt == sink) return limit[sink];
q.push(nxt);
}
}
}
return -1;
}
int edmondsKarp(int src, int sink) {
int totalFlow = 0;
while (true) {
int pathFlow = bfsSearch(src, sink);
if (pathFlow == -1) break;
totalFlow += pathFlow;
int cur = sink;
while (cur != src) {
int p = parent[cur];
grid[p][cur] -= pathFlow;
grid[cur][p] += pathFlow;
cur = p;
}
}
return totalFlow;
}
int main() {
int u, v, w;
while (cin >> connections >> nodes) {
memset(grid, 0, sizeof(grid));
while (connections--) {
cin >> u >> v >> w;
grid[u][v] += w;
}
cout << edmondsKarp(1, nodes) << endl;
}
return 0;
}
3. Dinic's Algorithm
Dinic's algorithm uses BFS to construct a level graph (layering nodes by distance from source) and then uses DFS to send flow within that layered structure. It often includes "current arc" optimization to avoid re-checking edges.
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 210;
const int INF = 1e9;
struct Edge {
int to, cap, rev;
};
vector<Edge> adj[MAXN];
int level[MAXN], ptr[MAXN];
int n, m;
void addEdge(int u, int v, int c) {
adj[u].push_back({v, c, (int)adj[v].size()});
adj[v].push_back({u, 0, (int)adj[u].size() - 1});
}
bool bfsLevel(int src, int sink) {
memset(level, -1, sizeof(level));
queue<int> q;
level[src] = 0;
q.push(src);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& e : adj[u]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return level[sink] >= 0;
}
int dfsFlow(int u, int sink, int f) {
if (u == sink) return f;
for (int& i = ptr[u]; i < adj[u].size(); i++) {
Edge& e = adj[u][i];
if (e.cap > 0 && level[e.to] == level[u] + 1) {
int pushed = dfsFlow(e.to, sink, min(f, e.cap));
if (pushed > 0) {
e.cap -= pushed;
adj[e.to][e.rev].cap += pushed;
return pushed;
}
}
}
return 0;
}
int dinicMaxFlow(int src, int sink) {
int flow = 0;
while (bfsLevel(src, sink)) {
memset(ptr, 0, sizeof(ptr));
while (int pushed = dfsFlow(src, sink, INF)) {
flow += pushed;
}
}
return flow;
}
int main() {
int u, v, w;
while (cin >> m >> n) {
for (int i = 1; i <= n; i++) adj[i].clear();
while (m--) {
cin >> u >> v >> w;
addEdge(u, v, w);
}
cout << dinicMaxFlow(1, n) << endl;
}
return 0;
}