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 between greedy selection and dynamic programming that pervades discrete optimization.

Weighted Graphs and Distance

For a walk \(P = (v_0, v_1, \ldots, v_k)\) in a weighted digraph, 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\inf_{P \,:\, s \leadsto t} w(P) & \text{if a walk from } s \text{ to } t \text{ exists,} \\ +\infty & \text{otherwise,} \end{cases} \] where the infimum is taken over all walks \(P\) from \(s\) to \(t\).

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)\). With non-negative weights, the infimum is also attained by a path, since removing a cycle from a walk does not increase its weight and there are only finitely many paths. If all weights are positive, so that \(\delta(s,t) = 0\) only when \(s = t\), then \(\delta\) is a quasi-metric (or asymmetric metric) on the vertex set, possibly taking the value \(+\infty\). It is not a metric in the strict sense, since a metric requires symmetry by definition. When negative weights are present, \(\delta(s,t) = -\infty\) exactly when some walk from \(s\) to \(t\) passes through a vertex of a negative-weight cycle, since going around the cycle repeatedly makes the weight arbitrarily negative. Otherwise every cycle met by such a walk can be excised without increasing the weight, so the infimum is a minimum over finitely many paths.

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 and lets tentative distances improve over \(|V|-1\) rounds.

For the subproblems, let \(d_i[v]\) be the minimum weight of any walk 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\). When \(\delta(s,v) \gt -\infty\), a minimum-weight walk from \(s\) to \(v\) can be taken to be a path, which has at most \(|V| - 1\) edges, so \(\delta(s,v) = d_{|V|-1}[v]\). The proof below makes this precise.

The Bellman-Ford recurrence is a canonical instance of DP. Its optimal substructure is that a minimum-weight walk from \(s\) to \(v\) with at most \(i\) edges is either a minimum-weight walk with at most \(i-1\) edges, or the extension of some minimum-weight walk 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|)\), since 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 and exploits the monotonicity of non-negative weights for superior runtime. Bellman-Ford's DP approach defers commitment and explores all possible relaxations. It is 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 AI. In these settings, 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 for a flow \(f^*\) of maximum value \(|f^*|\). Since the objective \(|f|\) and all constraints are linear in the flow variables, this is a linear program, 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) \gt 0\) by pushing \(\Delta\) units along \(P\). An edge \((u,v)\) of \(G_f\) with \((u,v) \in E\) is a forward edge, and an edge \((v,u)\) of \(G_f\) with \((u,v) \in E\) is a backward edge, which corresponds to an original edge \((u,v)\) carrying positive flow. Pushing means that each forward edge \((u,v)\) of \(P\) has \(f(u,v)\) increased by \(\Delta\), and each backward edge \((v,u)\) of \(P\) has \(f(u,v)\) decreased by \(\Delta\). The result is again a flow, of value \(|f| + \Delta\). Since \(\Delta \leq c_f(e)\) for every \(e \in P\), each \(f(e)\) stays in \([0, c(e)]\). At each inner vertex of \(P\), the edge of \(P\) entering it raises the net inflow by \(\Delta\) (a forward edge adds flow into the vertex, a backward edge removes flow out of it), and the edge of \(P\) leaving it lowers the net inflow by \(\Delta\), so conservation is preserved. Finally, \(P\) leaves \(s\) along its first edge and never returns to \(s\), which raises \(|f|\) by \(\Delta\). When the augmenting path traverses a backward edge \((v,u)\), pushing flow along it effectively cancels previously assigned flow on \((u,v)\) and redirects 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 termination of the Ford-Fulkerson method depends on the capacity values. With integer capacities, the flow stays integer-valued, so every residual capacity is an integer and each augmentation increases \(|f|\) by at least 1. Since \(|f|\) is bounded above by the capacity of any cut, as we show below, the procedure terminates after finitely many steps. Rational capacities reduce to this case after multiplying all capacities by a common denominator. With irrational capacities, however, examples exist where the method runs forever without converging to the maximum flow. The Edmonds-Karp variant resolves this entirely, since the BFS choice forces termination in \(O(|V| \cdot |E|)\) augmentations regardless of capacity values. We state the Edmonds-Karp bounds without proof.

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, we expand \(\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), and the two cancel. 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 next theorem shows that equality is attained.

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, and it shows 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 the directed graphs of the two preceding sections. The choice is not merely presentational. 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\). Each row of \(P\) sums to 1, so \(P\) is a row-stochastic matrix. Equivalently, \(P^\top\) is stochastic in the column convention, where the columns are probability vectors. 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

Under the stationary distribution, the walker is found at each vertex with probability proportional to its degree. High-degree "hub" vertices are visited more frequently, and this fact 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\) (that is, \(L_{\text{rw}} \mathbf{f}(v) = 0\)) precisely when its value equals the average over its neighbors. This is the discrete analogue of the mean value property that characterizes harmonic functions in continuous analysis.

The eigenvalues of \(P\) are real, since \(P = D^{-1}A\) is similar to the symmetric matrix \(D^{-1/2} A D^{-1/2}\). They have modulus at most 1 by the spectral radius of a stochastic matrix applied to \(P^\top\), which has the same eigenvalues. We list them as \(1 = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq -1\), so the eigenvalues of \(L_{\text{rw}}\) are \(\mu_i = 1 - \lambda_i\) with \(0 = \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n\). The eigenvalue 1 is simple, since its eigenspace is one-dimensional by the uniqueness argument above, and the similarity to a symmetric matrix makes algebraic and geometric multiplicities agree. Moreover, and \(\lambda_n \gt -1\) exactly when \(G\) is non-bipartite. On a bipartite graph, by contrast, \(\lambda_n = -1\). A walk started at a single vertex alternates between the two vertex classes with period 2, so its distribution does not converge. 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\) and \(\|\boldsymbol{\mu} - \boldsymbol{\nu}\|_{\text{TV}} = \frac{1}{2}\sum_{v} |\mu_v - \nu_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 characterization of \(\lambda_n = -1\) by bipartiteness and the mixing time bound belong to the standard theory of stochastic matrices and Markov chains, and we state them without proof.

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}\). It shares the eigenvalues \(\mu_1 = 0 \lt \mu_2 \leq \cdots \leq \mu_n\) of \(L_{\text{rw}}\). 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 vectors 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|\).

The right-hand side is precisely the squared Euclidean distance in a spectral embedding weighted by \(1/\mu_k\). It forms 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. We state it without proof, since the derivation requires the electrical-network interpretation of random walks, which is beyond the scope of this page.