Network Flow & Walks on Graphs

Shortest Paths

In Introduction to Graph Theory, we defined paths and studied their combinatorial structure. We now equip our graphs with weights and ask a quantitative question: among all paths connecting two vertices, which one minimizes total weight? This is the shortest path problem, and its study reveals a fundamental dichotomy in algorithm design — greedy selection versus dynamic programming — that pervades discrete optimization.

Weighted Graphs and Distance

For a directed path \(P = (v_0, v_1, \ldots, v_k)\), we define its weight as \[ w(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1}). \] (In the boundary case \(k = 0\), the sum is empty and \(w(P) = 0\).) The shortest-path distance from \(s\) to \(t\) is \[ \delta(s, t) = \begin{cases} \displaystyle\min_{P \,:\, s \leadsto t} w(P) & \text{if a path from } s \text{ to } t \text{ exists,} \\ +\infty & \text{otherwise.} \end{cases} \] When all weights are non-negative, \(\delta\) satisfies the triangle inequality \(\delta(s,t) \leq \delta(s,u) + \delta(u,t)\) and non-negativity \(\delta(s,t) \geq 0\), but on a directed graph it is generally not symmetric: \(\delta(s,t) \neq \delta(t,s)\). Thus \(\delta\) is a quasi-metric (or asymmetric metric) on the vertex set, not a metric in the strict sense — recall that a metric requires symmetry by definition. When negative weights are present, \(\delta(s,t)\) may be \(-\infty\) if a negative-weight cycle is reachable from \(s\) on a path to \(t\).

Dijkstra's Algorithm

When all edge weights are non-negative, the shortest-path problem admits a greedy solution. Dijkstra's algorithm maintains a set \(S\) of vertices whose shortest-path distances from a source \(s\) have been finalized, and repeatedly extracts the vertex with the smallest tentative distance.

With a binary min-heap, each extract-min costs \(O(\log |V|)\) worst-case and each decrease-key costs \(O(\log |V|)\) worst-case. Since we perform \(|V|\) extractions and at most \(|E|\) relaxations, the total running time is \[ O\bigl((|V| + |E|) \log |V|\bigr). \] With a Fibonacci heap, decrease-key is amortized \(O(1)\), yielding \(O(|V| \log |V| + |E|)\).

The greedy strategy works precisely because non-negative weights guarantee that extending a path can never decrease its total weight — once a vertex is finalized, no future path can improve upon it. This monotonicity breaks when negative edges are present.

Bellman-Ford Algorithm and Dynamic Programming

The Bellman-Ford algorithm handles arbitrary real-valued weights (including negative edges) by adopting a fundamentally different strategy: rather than greedily committing to final distances, it iteratively relaxes all edges, allowing tentative distances to improve over \(|V|-1\) rounds.

Define the subproblems: let \(d_i[v]\) be the minimum weight of any path from \(s\) to \(v\) using at most \(i\) edges. The recurrence is \[ d_i[v] = \min\Bigl(\, d_{i-1}[v], \;\min_{(u,v) \in E} \bigl(d_{i-1}[u] + w(u,v)\bigr)\Bigr), \] with base case \(d_0[s] = 0\) and \(d_0[v] = +\infty\) for \(v \neq s\). Since any shortest path in a graph without negative cycles has at most \(|V| - 1\) edges, we have \(\delta(s,v) = d_{|V|-1}[v]\).

The Bellman-Ford recurrence is a canonical instance of DP: the optimal substructure is that a shortest path from \(s\) to \(v\) with at most \(i\) edges is either a shortest path with at most \(i-1\) edges, or the extension of some shortest path to a predecessor \(u\) by the edge \((u,v)\). The overlapping subproblems arise because multiple vertices may share the same predecessors.

The total running time is \(O(|V| \cdot |E|)\): we perform \(|V| - 1\) passes over all \(|E|\) edges.

Greedy vs. Dynamic Programming

Dijkstra and Bellman-Ford embody the two great paradigms of discrete optimization. Dijkstra's greedy approach commits irrevocably to each vertex's distance, exploiting the monotonicity of non-negative weights for superior runtime. Bellman-Ford's DP approach defers commitment, exploring all possible relaxations — slower, but correct under weaker assumptions. This trade-off between exploiting structural assumptions for speed and maintaining generality recurs throughout algorithm design and optimization theory.

A natural extension of the greedy paradigm is the A* algorithm, which augments Dijkstra's strategy with a heuristic function \(h(v)\) estimating the remaining distance from \(v\) to the goal. Instead of extracting the vertex minimizing \(d[v]\), A* extracts the vertex minimizing \(d[v] + h(v)\), directing the search toward the target. When \(h\) is admissible (never overestimates true distance) and consistent (satisfies a triangle inequality), A* retains optimality while dramatically reducing the number of vertices explored. This makes A* the algorithm of choice for robotic path planning, autonomous navigation, and game ML — settings where spatial heuristics provide powerful guidance that pure Dijkstra cannot exploit.

Maximum Flow

We now pass from finding an optimal single path to optimizing the aggregate throughput of an entire network. Where shortest paths ask "what is the cheapest route?", maximum flow asks "how much can we push through simultaneously?" This shift — from a path problem to a network problem — opens the door to deep connections with linear programming duality.

Flow Networks

The maximum flow problem asks: find a flow \(f^*\) of maximum value \(|f^*|\). This is a linear program — the objective \(|f|\) and all constraints are linear in the flow variables — and we shall see that its dual yields the min-cut theorem.

Residual Graphs and Augmenting Paths

An augmenting path is a path from \(s\) to \(t\) in the residual graph \(G_f\). If such a path \(P\) exists, we can increase the flow by \(\Delta = \min_{e \in P} c_f(e) > 0\) by pushing \(\Delta\) units along \(P\). When the augmenting path traverses a backward edge \((v,u)\) — corresponding to an original edge \((u,v)\) carrying positive flow — pushing flow along it effectively cancels previously assigned flow on \((u,v)\), redirecting that capacity to a more profitable route. This ability to "undo" earlier decisions is precisely what allows the method to escape locally suboptimal flow assignments and converge to a global maximum.

The method terminates when no augmenting path exists in \(G_f\). The choice of augmenting path determines both the algorithm's name and its complexity. When augmenting paths are found via breadth-first search (choosing a shortest path in terms of number of edges), the method is called the Edmonds-Karp algorithm, with running time \(O(|V| \cdot |E|^2)\).

The Ford-Fulkerson method's termination depends on the capacity values: with integer (or rational) capacities, each augmentation increases \(|f|\) by at least the capacity unit, so the procedure terminates in finitely many steps; with irrational capacities, however, examples exist where the method runs forever without converging to the maximum flow. The Edmonds-Karp variant resolves this entirely — the BFS choice forces termination in \(O(|V| \cdot |E|)\) augmentations regardless of capacity values.

The Max-Flow Min-Cut Theorem

For any flow \(f\) and any \(s\)-\(t\) cut \((S,T)\), the value \(|f|\) equals the net flow across the cut. To see this, define the net out-flow at each vertex, \[ b_f(v) \;=\; \sum_{(v,w) \in E} f(v,w) \;-\; \sum_{(u,v) \in E} f(u,v). \] Conservation gives \(b_f(v) = 0\) for all \(v \in V \setminus \{s, t\}\), and \(b_f(s) = |f|\) by definition. Since \(t \notin S\), summing \(b_f\) over \(v \in S\) yields \[ \sum_{v \in S} b_f(v) \;=\; b_f(s) \;+\; \sum_{v \in S \setminus \{s\}} b_f(v) \;=\; |f|. \] On the other hand, expanding \(\sum_{v \in S} b_f(v)\) edge-by-edge: every edge \((a,b)\) with both endpoints in \(S\) contributes \(+f(a,b)\) (from \(a\)'s out-sum) and \(-f(a,b)\) (from \(b\)'s in-sum), cancelling; every edge with both endpoints in \(T\) contributes nothing; only edges crossing the cut survive: \[ |f| = \sum_{\substack{(u,v) \in E \\ u \in S,\; v \in T}} f(u,v) \;-\; \sum_{\substack{(v,u) \in E \\ v \in T,\; u \in S}} f(v,u). \] Combining \(f(u,v) \leq c(u,v)\) on the first sum and \(f(v,u) \geq 0\) on the second, \[ |f| \;\leq\; \sum_{\substack{(u,v) \in E \\ u \in S,\; v \in T}} c(u,v) \;=\; c(S,T). \] Every flow value is bounded above by every cut capacity. The remarkable fact is that equality is achieved.

Random Walks on Graphs

So far, we have studied deterministic optimization on graphs: finding shortest paths and maximum flows. We now introduce stochastic dynamics by considering a particle that traverses a graph randomly. This probabilistic perspective connects graph theory to Markov chains and spectral graph theory, revealing that combinatorial and algebraic properties of a graph are two faces of the same coin.

Throughout this section we work with undirected graphs, in contrast to Sections 1 and 2 above. This is not merely a presentational choice: the closed-form stationary distribution \(\pi_v = \deg(v)/(2m)\) and the symmetry of the graph Laplacian both rely on the undirected structure, where adjacency is reciprocal.

The Transition Matrix

Let \(A\) be the adjacency matrix and \(D = \operatorname{diag}(\deg(v_1), \ldots, \deg(v_n))\) the degree matrix. The transition matrix of the random walk is \[ P = D^{-1}A. \] The entry \(P_{uv} = A_{uv}/\deg(u)\) is exactly the one-step transition probability from \(u\) to \(v\). Note that \(P\) is a row-stochastic matrix: each row sums to 1. After \(k\) steps, the distribution of the walker's position evolves as \[ \boldsymbol{\pi}^{(k)} = \boldsymbol{\pi}^{(0)} P^k, \] where \(\boldsymbol{\pi}^{(0)}\) is the initial distribution (a row vector).

Stationary Distribution

The result is elegant in its simplicity: in the long run, the random walker visits each vertex in proportion to its degree. High-degree "hub" vertices are visited more frequently — a fact that underpins the intuition behind centrality measures in network science.

The Random Walk Laplacian

The transition matrix is intimately connected to the graph Laplacian. Recall that the (combinatorial) graph Laplacian is \(L = D - A\). The random walk Laplacian is defined as \[ L_{\text{rw}} = D^{-1}L = I - D^{-1}A = I - P. \] This operator satisfies \(L_{\text{rw}} \mathbf{f} = \mathbf{f} - P\mathbf{f}\), so its action on a function \(\mathbf{f} \colon V \to \mathbb{R}\) measures the difference between \(\mathbf{f}\) and its local average under the random walk: \[ (L_{\text{rw}} \mathbf{f})(v) = f(v) - \frac{1}{\deg(v)} \sum_{u \,:\, (u,v) \in E} f(u). \] A function is harmonic at \(v\) (i.e., \(L_{\text{rw}} \mathbf{f}(v) = 0\)) precisely when its value equals the average over neighbors — the discrete analogue of the mean value property that characterizes harmonic functions in continuous analysis.

The eigenvalues of \(L_{\text{rw}}\) are \(0 = \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n\), where \(\mu_i = 1 - \lambda_i\) and \(1 = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n > -1\) are the eigenvalues of \(P\) (the lower bound \(\lambda_n > -1\) holds because the graph is non-bipartite). On a bipartite graph, by contrast, \(\lambda_n = -1\): the walker oscillates between the two vertex classes with period 2, so the distribution never settles but instead alternates indefinitely — this is the spectral signature of periodicity. The rate of convergence to stationarity is controlled by \[ \bar{\lambda} = \max\bigl(|\lambda_2|,\, |\lambda_n|\bigr), \] which captures contributions from both the second-largest and the most negative eigenvalue. The standard mixing time bound is \[ \|\boldsymbol{\pi}^{(k)} - \boldsymbol{\pi}\|_{\text{TV}} \leq \frac{1}{2}\sqrt{\frac{1}{\pi_{\min}}}\;\bar{\lambda}^{\,k}, \] where \(\pi_{\min} = \min_v \pi_v\). The quantity \(1 - \bar{\lambda}\) is the absolute spectral gap: a large gap means rapid mixing, while a small gap means the walk remains trapped in local clusters for long periods. The spectral facts of this paragraph belong to the standard theory of stochastic matrices and Markov chains; detailed proofs are given in the dedicated treatments of stochastic matrices and Markov chains.

Hitting Time and Commute Time

These quantities admit a spectral characterization. Since \(L_{\text{rw}} = D^{-1}L\) is generally not symmetric, we work with the similar symmetric matrix \(L_{\text{sym}} = D^{-1/2} L\, D^{-1/2} = I - D^{-1/2} A\, D^{-1/2}\), which shares the same eigenvalues \(\mu_1 = 0 < \mu_2 \leq \cdots \leq \mu_n\). Let \(\boldsymbol{\psi}_1, \ldots, \boldsymbol{\psi}_n\) be an orthonormal eigenbasis of \(L_{\text{sym}}\) (in the standard Euclidean inner product), and define \(\boldsymbol{\phi}_k = D^{-1/2}\boldsymbol{\psi}_k\) — these are the right eigenvectors of \(L_{\text{rw}}\), orthonormal with respect to the \(D\)-weighted inner product \(\langle \boldsymbol{\phi}_j, \boldsymbol{\phi}_k \rangle_D = \boldsymbol{\phi}_j^\top D\, \boldsymbol{\phi}_k = \delta_{jk}\). Under this normalization, \[ C(u,v) = 2m \sum_{k=2}^{n} \frac{1}{\mu_k}\bigl(\phi_k(u) - \phi_k(v)\bigr)^2, \] where \(m = |E|\). This is precisely the squared Euclidean distance in a spectral embedding weighted by \(1/\mu_k\) — a direct bridge between the combinatorial notion of "distance by random traversal" and the algebraic notion of "distance in eigenspace." This identity is the commute-time formula (Lovász's 1993 survey on random walks); we state it without proof, as the derivation requires the electrical-network interpretation of random walks beyond the scope of this page.