Network flow: shortest path, minimal spanning tree, maximal flow

Why it matters

Plant layouts, material-handling routes, pipelines, power and data cables, and supply chains are all networks of nodes and arcs. Three classic questions cover most of their design: the cheapest or quickest route between two points (shortest path), the cheapest way to connect every point (minimal spanning tree), and the most material that can be pushed through limited capacities (maximal flow). Each has a simple, exact hand algorithm.

Key ideas

Vocabulary. A network has nodes (vertices) and arcs or edges, each with a length, cost or capacity. Arcs may be directed (one-way) or undirected. A path is a sequence of connected arcs; a cycle returns to its start; a tree is a connected network with no cycle; a spanning tree connects all n nodes using exactly n − 1 edges.

Shortest path — Dijkstra's algorithm (all arc lengths ≥ 0).

1. Give the source a permanent label 0; all other nodes a temporary label ∞.
2. From the most recently made permanent node u, update each neighbour v: label(v) = min(label(v), label(u) + l(u, v)), recording the predecessor.
3. Make the smallest temporary label permanent. Repeat until the destination (or every node) is permanent.
4. Trace predecessors back to read the route. A permanent label is final because all arc lengths are non-negative. With negative arcs use Bellman–Ford (which also detects negative cycles).

Minimal spanning tree (MST).

• Kruskal: sort edges by weight; add the next lightest edge if it does not form a cycle; stop at n − 1 edges.
• Prim: start at any node; repeatedly add the lightest edge joining the connected set to a new node. Both are greedy and exact. The MST minimises total edge length, not the distance between any particular pair of nodes — it is not a shortest-path tree.

Maximal flow — Ford–Fulkerson (augmenting paths).

1. Start with zero flow.
2. Find a path from source to sink on which every arc has residual capacity > 0 (forward arcs: capacity − flow; reverse arcs: flow already sent, which can be cancelled).
3. Send the bottleneck (smallest residual) along the path and update residuals.
4. Repeat until no augmenting path exists. Flow is conserved at every intermediate node (in = out). Choosing the shortest augmenting path each time (Edmonds–Karp) guarantees a polynomial number of steps.

Max-flow min-cut theorem. A cut separates the source from the sink; its capacity is the sum of capacities of arcs going from the source side to the sink side. The maximum flow equals the minimum cut capacity. The min cut identifies the bottleneck arcs worth expanding.

Formulas

• Dijkstra update: d(v) = min{ d(v), d(u) + l(u, v) }
• Edges in a spanning tree: n − 1
• Flow conservation at node k (not source/sink): Σ f(i, k) = Σ f(k, j)
• Capacity limit: 0 ≤ f(i, j) ≤ c(i, j)
• Bottleneck of a path: δ = min residual capacity on the path
• Max-flow min-cut: max flow value = min over cuts of Σ c(i, j), i on source side, j on sink side

Symbols: d(v) = current shortest-distance label of node v (km, min, ₹); l(u, v) = arc length; n = number of nodes; f(i, j) = flow on arc i→j (units/h); c(i, j) = arc capacity (units/h).

Worked examples

Example 1 (shortest path and MST on the same network). Undirected edges (km): 1–2: 7, 1–3: 9, 1–6: 14, 2–3: 10, 2–4: 15, 3–4: 11, 3–6: 2, 4–5: 6, 5–6: 9. Find the shortest route from 1 to 5 and the MST.

1. Permanent 1 (0). Temporary: 2 = 7, 3 = 9, 6 = 14.
2. Make 2 permanent (7). Update: 3 via 2 = 17 (keep 9), 4 = 7 + 15 = 22.
3. Make 3 permanent (9). Update: 4 = min(22, 9 + 11) = 20, 6 = min(14, 9 + 2) = 11.
4. Make 6 permanent (11). Update: 5 = 11 + 9 = 20.
5. Make 4 (20) and 5 (20) permanent. Predecessors of 5: 6 → 3 → 1.
6. Shortest route 1–3–6–5, length 20 km.
7. Kruskal for the MST: 3–6 (2) ✓, 4–5 (6) ✓, 1–2 (7) ✓, 1–3 (9) ✓, 5–6 (9) ✓ — five edges for six nodes, stop (2–3 and 3–4 would close cycles). MST length = 2 + 6 + 7 + 9 + 9 = 33 km.

Example 2 (GATE-type maximal flow). Directed capacities (units/h): S→A 10, S→B 8, A→B 2, A→C 6, A→T 5, B→C 7, C→T 9. Find the maximum flow from S to T.

1. Path S–A–T: bottleneck min(10, 5) = 5. Flow = 5. Residual: S→A 5, A→T 0.
2. Path S–A–C–T: bottleneck min(5, 6, 9) = 5. Flow = 10. Residual: S→A 0, A→C 1, C→T 4.
3. Path S–B–C–T: bottleneck min(8, 7, 4) = 4. Flow = 14. Residual: C→T 0.
4. No path remains: both arcs into T (A→T and C→T) are saturated.
5. Min cut: {S, A, B, C} | {T} with capacity 5 + 9 = 14, equal to the flow.
6. Maximum flow = 14 units/h. Raising A→T or C→T capacity is the only way to increase it.

Common mistakes

• Making a node permanent before it has the smallest temporary label, or using Dijkstra with negative arcs.
• Confusing the MST with the shortest path: the MST route between two nodes is generally not their shortest path.
• Adding an edge in Kruskal that closes a cycle, or stopping before n − 1 edges.
• In max flow, forgetting reverse (cancellation) arcs, which can stop the algorithm too early.
• Counting arcs that point from the sink side back to the source side in a cut capacity.
• Assuming the source's out-arc capacities give the max flow; the bottleneck may be anywhere.

For GATE PI

• Shortest distance between two nodes in a 6–8 node network by Dijkstra (NAT).
• MST total length by Kruskal or Prim; number of edges in a spanning tree.
• Maximum flow and identifying the minimum cut.
• Practise keeping a clean label table — most errors are bookkeeping, not concept.

Quick check

1. How many edges does a spanning tree of 9 nodes have?
2. Why can Dijkstra not be used with negative arc lengths?
3. A cut's forward arcs have capacities 4, 6 and 5. What is the most the max flow can be?
4. Does Kruskal's algorithm work when some edge weights are negative?

Answers: 1. 8. 2. A permanent label could later be improved through a negative arc, breaking the algorithm's logic. 3. 15 (any cut is an upper bound on the flow). 4. Yes — only the order of the weights matters.