56 Graphs and networks

Paths, flows, and spanning structures

You want to drive from Edmonton to Calgary in the least time, not just the fewest kilometres. You need to wire up five remote sensors to a data logger using as little cable as possible. You want to know the maximum throughput a pipeline network can deliver before a bottleneck binds.

Different questions. The same underlying structure: nodes, connections, weights. Once you have that structure, a handful of classical algorithms — each with a clean proof of correctness — answer all of them.

56.1 Graph fundamentals

A graph \(G = (V, E)\) — read “a graph G consisting of vertex set V and edge set E” — is a set of vertices (also called nodes) \(V\) together with a set of edges \(E\), where each edge connects two vertices.

In an undirected graph, the edge \(\{u, v\}\) can be traversed in either direction. In a directed graph (digraph), each edge \((u, v)\) — read “from u to v” — has a direction: you can go from \(u\) to \(v\) but not necessarily back.

A weighted graph assigns a real number \(w(u, v)\) — “the weight of the edge from \(u\) to \(v\)” — to each edge. Weights model distance, cost, travel time, capacity, or any other quantity associated with a connection.

56.1.1 Adjacency matrix

The adjacency matrix \(A\) of a graph on \(n\) vertices is the \(n \times n\) matrix where entry \(A_{ij} = 1\) if there is an edge from vertex \(i\) to vertex \(j\), and \(A_{ij} = 0\) otherwise. For a weighted graph, replace the 1 with the edge weight. For an undirected graph, \(A\) is symmetric: \(A_{ij} = A_{ji}\).

Example: a simple undirected graph with four vertices \(\{1, 2, 3, 4\}\) and edges \(\{1,2\}\), \(\{1,3\}\), \(\{2,4\}\), \(\{3,4\}\) has adjacency matrix

\[A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}.\]

56.1.2 Degree, paths, and connectivity

The degree \(d(v)\) — “the degree of vertex \(v\)” — is the number of edges incident to \(v\). In the example above, \(d(1) = 2\), \(d(2) = 2\), \(d(3) = 2\), \(d(4) = 2\).

A path from \(u\) to \(v\) is a sequence of vertices starting at \(u\) and ending at \(v\) where consecutive vertices are connected by an edge, and no vertex repeats. A cycle is a closed path: it starts and ends at the same vertex. A graph is connected if there is a path between every pair of vertices.

A tree is a connected graph with no cycles. Equivalently, a tree on \(n\) vertices has exactly \(n-1\) edges — removing any edge disconnects it, adding any edge creates a cycle. Trees are the minimal connected structures, which is exactly why they appear in spanning problems.

56.2 Shortest path: Dijkstra’s algorithm

Problem. Given a weighted graph with non-negative edge weights and a source vertex \(s\), find the shortest-distance path from \(s\) to every other vertex.

Algorithm. Maintain a set \(S\) of vertices whose shortest distances are finalised, and for every vertex outside \(S\), a tentative distance \(\text{dist}[v]\). Initially \(\text{dist}[s] = 0\) and \(\text{dist}[v] = \infty\) for all \(v \neq s\).

Repeat until \(S = V\):

Pick the vertex \(u \notin S\) with the smallest \(\text{dist}[u]\).
Add \(u\) to \(S\) (its distance is now final).
For each neighbour \(v\) of \(u\): if \(\text{dist}[u] + w(u,v) < \text{dist}[v]\), update \(\text{dist}[v] \leftarrow \text{dist}[u] + w(u,v)\).

56.2.1 Worked trace — 6-node graph

Consider the following undirected weighted graph with vertices \(\{A, B, C, D, E, F\}\) and source \(A\):

Edge	Weight
A–B	4
A–C	2
B–C	5
B–D	10
C–E	3
E–D	4
D–F	11
E–F	7

Initial distances: \(A=0\), \(B=\infty\), \(C=\infty\), \(D=\infty\), \(E=\infty\), \(F=\infty\).

Step 1. Smallest tentative distance is \(A\) (dist = 0). Finalise \(A\). Update neighbours: \(\text{dist}[B] \leftarrow 4\), \(\text{dist}[C] \leftarrow 2\).

Step 2. Smallest non-finalised: \(C\) (dist = 2). Finalise \(C\). Update neighbours: \(B\): \(2+5=7 > 4\), no change. \(E\): \(2+3=5 \leftarrow 5\).

Step 3. Smallest non-finalised: \(B\) (dist = 4). Finalise \(B\). Update neighbours: \(C\): already finalised. \(D\): \(4+10=14 \leftarrow 14\).

Step 4. Smallest non-finalised: \(E\) (dist = 5). Finalise \(E\). Update neighbours: \(D\): \(5+4=9 < 14\), update \(\text{dist}[D] \leftarrow 9\). \(F\): \(5+7=12 \leftarrow 12\).

Step 5. Smallest non-finalised: \(D\) (dist = 9). Finalise \(D\). Update neighbours: \(F\): \(9+11=20 > 12\), no change.

Step 6. Smallest non-finalised: \(F\) (dist = 12). Finalise \(F\).

Final shortest distances from \(A\): \(B=4\), \(C=2\), \(D=9\), \(E=5\), \(F=12\).

The shortest path to \(F\) is \(A \to C \to E \to F\) with total weight \(2+3+7=12\).

56.2.2 Correctness sketch

Dijkstra is a greedy algorithm. Before the proof, it’s worth asking: why would the greedy choice ever go wrong? The answer is: it could go wrong if a later, distant vertex \(y\) had a shortcut that made a longer-looking path to \(u\) end up shorter. Non-negative edge weights prevent exactly this — you can never shorten a path by adding edges.

The key claim: when a vertex \(u\) is moved into \(S\), its tentative distance \(\text{dist}[u]\) is the true shortest distance.

Proof by contradiction: suppose some path to \(u\) is shorter, and let \(y\) be the first vertex on that path not yet in \(S\) when \(u\) is picked. The portion of that path from the source to \(y\) has length \(\text{dist}[y]\) (since Dijkstra has already found the shortest path to \(y\), which lies on our assumed shorter path). Any further edges from \(y\) to \(u\) have non-negative weight, so the full path is at least \(\text{dist}[y]\) in length. But \(\text{dist}[y] \geq \text{dist}[u]\), because Dijkstra would have picked \(y\) before \(u\) if \(y\) were closer. So the assumed shorter path is at least as long as \(\text{dist}[u]\) — a contradiction.

This argument fails if any edge weight is negative — a later edge could make up for a large earlier one. For graphs with negative weights (but no negative-weight cycles), Bellman-Ford is the correct algorithm: it relaxes all edges \(|V|-1\) times, running in \(O(|V||E|)\) time rather than Dijkstra’s \(O((|V| + |E|) \log |V|)\). One use case is currency arbitrage detection.

56.3 Minimum spanning tree

Problem. Given a connected weighted undirected graph, find a spanning tree — a tree that includes all vertices — with minimum total edge weight.

Two classical algorithms solve this; both are correct, and both rely on the same underlying property.

56.3.1 Cut property

A cut is a partition of \(V\) into two non-empty sets \(S\) and \(V \setminus S\). An edge crosses the cut if one endpoint is in \(S\) and the other is in \(V \setminus S\). The cut property states: for any cut \((S, V \setminus S)\), if \(e\) is the unique minimum-weight edge crossing that cut, then \(e\) belongs to every minimum spanning tree; more generally, any minimum-weight edge crossing a given cut belongs to some minimum spanning tree. This is the single fact both Kruskal and Prim exploit.

Here is how this applies: in Kruskal’s algorithm, every time we consider an edge \(e = \{u,v\}\), the two components containing \(u\) and \(v\) define a cut. The edge \(e\) is the cheapest edge crossing that cut (because we process edges in weight order and skip any that close a cycle). The cut property says it is safe to include \(e\) in the MST. Every addition Kruskal makes is justified by exactly this argument.

56.3.2 Kruskal’s algorithm

Sort all edges by weight (ascending).
Initialise \(T = \emptyset\) (no edges selected yet).
Consider edges in order. Add edge \(e = \{u, v\}\) to \(T\) if it does not create a cycle (equivalently, if \(u\) and \(v\) are in different connected components of \(T\)).
Stop when \(T\) has \(n-1\) edges.

Use a union-find data structure to test and merge components efficiently. Total time: \(O(|E| \log |E|)\) (dominated by sorting).

Worked example. Six-node graph with edges (sorted by weight):

Edge	Weight
C–E	3
A–C	2
A–B	4
E–D	4
B–C	5
E–F	7
B–D	10
D–F	11

Sorted: A–C (2), C–E (3), A–B (4), E–D (4), B–C (5), E–F (7), B–D (10), D–F (11).

Add A–C (2): no cycle. \(T = \{\)A–C\(\}\).
Add C–E (3): no cycle. \(T = \{\)A–C, C–E\(\}\).
Add A–B (4): no cycle. \(T = \{\)A–C, C–E, A–B\(\}\).
Add E–D (4): no cycle. \(T = \{\)A–C, C–E, A–B, E–D\(\}\).
Add B–C (5): creates cycle A–B–C–A. Skip.
Add E–F (7): no cycle. \(T = \{\)A–C, C–E, A–B, E–D, E–F\(\}\). Now \(|T| = 5 = n-1\). Done.

MST total weight: \(2+3+4+4+7 = 20\).

56.3.3 Prim’s algorithm

Start from an arbitrary seed vertex \(r\). Mark \(r\) as in the tree.
At each step, add the minimum-weight edge that connects a vertex inside the current tree to one outside it.
Repeat until all vertices are in the tree.

Worked example (same graph, starting from \(A\)):

Tree: \(\{A\}\). Cheapest crossing edge: A–C (2). Add C.
Tree: \(\{A, C\}\). Cheapest crossing edge: C–E (3). Add E.
Tree: \(\{A, C, E\}\). Cheapest crossing edge: A–B (4) or E–D (4). Take A–B. Add B.
Tree: \(\{A, C, E, B\}\). Cheapest crossing edge: E–D (4). Add D.
Tree: \(\{A, C, E, B, D\}\). Cheapest crossing edge: E–F (7). Add F.

MST edges: A–C, C–E, A–B, E–D, E–F. Total weight: 20. Same result as Kruskal.

Both algorithms always produce an MST. When the minimum-weight crossing edge for any cut is unique, the MST is unique. With ties, multiple MSTs of the same total weight may exist.

56.4 Network flows

Problem. A directed weighted graph has a distinguished source \(s\) (supply) and sink \(t\) (demand). Each directed edge \((u,v)\) has a capacity \(c(u,v) \geq 0\) — the maximum flow it can carry. The flow \(f(u,v)\) on each edge must satisfy:

Capacity constraint: \(0 \leq f(u,v) \leq c(u,v)\) for all edges.
Flow conservation: for every vertex \(v \neq s, t\), the total flow in equals the total flow out: \(\sum_u f(u,v) = \sum_w f(v,w)\).

The value of the flow is the total flow leaving \(s\) (equivalently, arriving at \(t\)). The problem is to maximise this value.

56.4.1 Ford-Fulkerson method

The key idea behind Ford-Fulkerson is that earlier routing decisions can be wrong, and the algorithm needs a way to undo them. If we sent flow along a path that turned out to block a better option, we want to be able to redirect it. The residual graph makes this possible by including a reverse edge for every forward edge: sending flow “backwards” on a reverse edge is equivalent to cancelling some previously routed flow.

Start with zero flow on all edges.
Find an augmenting path — any directed path from \(s\) to \(t\) in the residual graph \(G_f\), where edge \((u,v)\) has residual capacity \(c(u,v) - f(u,v)\) (how much more we can send forward) and the reverse edge \((v,u)\) has residual capacity \(f(u,v)\) (how much previously routed flow we can cancel).
Send as much flow along the augmenting path as the bottleneck edge allows.
Repeat until no augmenting path exists.

56.4.2 Max-flow min-cut theorem

A cut \((S, T)\) with \(s \in S\) and \(t \in T\) separates source from sink. The capacity of the cut is the sum of capacities of edges going from \(S\) to \(T\). The max-flow min-cut theorem states:

The maximum flow value equals the minimum cut capacity.

The forward direction is clear: no flow can exceed the capacity of any cut separating \(s\) from \(t\), because every unit of flow must cross the cut. The deep direction is that Ford-Fulkerson achieves this bound — when no augmenting path remains, the set of vertices reachable from \(s\) in the residual graph defines a cut whose capacity equals the current flow value.

In practice: to find the bottleneck in a network, find the minimum cut. The edges in the minimum cut are the ones whose capacity, if increased, would allow more total flow.

56.4.3 Worked example — 5-node network

Directed graph: source \(S\), sink \(T\), intermediate vertices \(A\), \(B\), \(C\).

Edge	Capacity
S→A	10
S→B	8
A→C	9
A→B	3
B→T	10
C→T	7
C→B	2

Round 1. Augmenting path \(S \to A \to C \to T\). Bottleneck: \(\min(10,9,7) = 7\). Send 7 units. Updated flows: S→A = 7, A→C = 7, C→T = 7.

Round 2. Augmenting path \(S \to A \to B \to T\). Bottleneck: \(\min(3,3,10) = 3\). Send 3 units. Updated flows: S→A = 10, A→B = 3, B→T = 3.

Round 3. Augmenting path \(S \to B \to T\). Bottleneck: \(\min(8,7) = 7\). Send 7 units. Updated flows: S→B = 7, B→T = 10.

Round 4. Path \(S \to A\): S→A is saturated (10/10). \(S \to B\): B→T is saturated (10/10). No augmenting path exists. Done.

Maximum flow = 7 + 3 + 7 = 17 units.

Minimum cut. After Round 3, the residual capacities are: S→A: 0, S→B: 1, A→C: 2, A→B: 0, B→T: 0, C→T: 0, C→B: 2, plus reverse edges A←S: 10, B←S: 7, C←A: 7, B←A: 3, T←B: 10, T←C: 7.

Starting from \(S\) in the residual graph: S→B has residual 1, so \(B\) is reachable. From \(B\): B→T has residual 0 (blocked); the reverse edge B←A carries residual 3, so \(A\) is reachable. From \(A\): A→C has residual 2, so \(C\) is reachable. From \(C\): C→T has residual 0 (blocked); C→B forward has residual 2 but \(B\) is already in the set.

Reachable set: \(\{S, B, A, C\}\). Non-reachable: \(\{T\}\).

The minimum cut consists of the edges crossing from \(\{S,B,A,C\}\) to \(\{T\}\): that is B→T (capacity 10) and C→T (capacity 7). Min cut capacity \(= 10 + 7 = 17\), which equals the max flow.

The minimum cut \(\{\)B→T, C→T\(\}\) identifies the bottleneck: these are the edges whose capacity limits the total throughput of the network.

Why Ford-Fulkerson terminates

With integer capacities, each augmentation increases the flow by at least 1. Since the flow is bounded above by the sum of capacities out of \(s\), the algorithm terminates. The reverse edges in the residual graph are what make it work correctly: they allow the algorithm to “undo” a routing decision and reroute flow along a more productive path.

56.5 Where this goes

The three problems in this chapter — shortest path, MST, network flow — are the foundational problems of combinatorial optimisation. They appear directly inside more complex algorithms: Dijkstra is the inner loop of many routing protocols; MST computation underlies Christofides’ approximation algorithm for the travelling salesman problem; max-flow is equivalent to maximum bipartite matching via a reduction. If you proceed to the study of algorithms or operations research, you will see all three again.

The other extension worth knowing is integer programming, where variables are constrained to take integer values. Many practical network problems — crew scheduling, facility location, vehicle routing — are integer programs. Chapter 1 of this section covered the continuous relaxation; the integer case is in general NP-hard, but the network structure of the problems above makes them tractable.

Where this shows up

A civil engineer routing roads or pipelines through terrain minimises a weighted path or tree.
A telecoms network engineer provisioning bandwidth uses max-flow to find the network’s throughput limit.
A supply-chain analyst models goods movement as a flow problem and finds bottleneck warehouse links.
A machine learning engineer working on graph neural networks needs the adjacency matrix representation as the input to the network.
A biologist mapping evolutionary relationships uses minimum spanning trees on genetic distance matrices.

56.6 Exercises

These are convergent problems. Each has a definite answer. The work is in applying the algorithm correctly and reading the result.

Exercise 1. Run Dijkstra’s algorithm on the following 5-node undirected weighted graph, starting from vertex \(P\).

Edge	Weight
P–Q	6
P–R	2
R–Q	3
R–S	7
Q–S	1
Q–T	5
S–T	4

Trace all distance updates. State the final shortest distance to each vertex and give the shortest path to \(T\).

Exercise 2. Find the MST of the following 6-node graph using Kruskal’s algorithm. List the edges in the order they are added to the tree and give the total MST weight.

Edge	Weight
1–2	7
1–3	5
2–4	8
2–3	9
3–4	15
3–5	6
4–5	4
4–6	5
5–6	2

Exercise 3. Find the MST of the same 6-node graph from Exercise 2 using Prim’s algorithm, starting from vertex 1. Verify that the total MST weight equals the result from Exercise 2.

Exercise 4. Find the maximum flow from \(S\) to \(T\) in the following 4-node network. Identify the minimum cut.

Edge	Capacity
S→A	8
S→B	6
A→T	5
A→B	4
B→T	9

Exercise 5. Let \(G\) be a tree on \(n\) vertices. Prove that the adjacency matrix \(A\) of \(G\) contains exactly \(n-1\) ones in each of its upper and lower triangular parts (i.e., \(G\) has exactly \(n-1\) edges), using only the definition of a tree as a connected acyclic graph.

Exercise 6 (Engineering application). A water treatment facility distributes purified water via a network of pipes from a treatment plant (source \(S\)) to a distribution reservoir (sink \(T\)). The intermediate pump stations are \(P\), \(Q\), \(R\).

Pipe	Capacity (ML/day)
S→P	12
S→Q	10
P→Q	3
P→R	8
Q→T	7
R→Q	4
R→T	9

Model this as a max-flow problem. Find the maximum daily throughput from \(S\) to \(T\) and identify the bottleneck cut — the set of pipes that, if their capacity were increased, would allow more water to reach \(T\).