I am covering the Maximum-Capacity Route problem here, which I also know by its more classical name, the widest path problem or bottleneck shortest path problem. Instead of minimizing total distance like typical shortest path problems, I am trying to find a path between two nodes that maximizes the minimum edge capacity along that path. I find this useful whenever the “weakest link” of a route matters more than the sum of its parts, such as when I care about the maximum amount of data, water, or goods that can flow continuously through a route without being bottlenecked by any single low-capacity segment.
History and Background
The widest path problem has roots in classical network flow theory, which was heavily developed in the 1950s by researchers including Lester Ford and Delbert Fulkerson, whose max-flow min-cut work laid much of the foundation for capacity-based network analysis. The specific single-path maximum bottleneck capacity problem was formalized as a variant of shortest path algorithms, adapted by replacing the usual “sum and minimize” logic with “minimum and maximize” logic. Because the structure so closely mirrors Dijkstra’s shortest path algorithm, most practical solutions I use today are direct adaptations of Dijkstra’s and Prim’s classical techniques, applied with a different combination operator.
Problem Statement
Given a weighted graph $G = (V, E, c)$ where each edge has a capacity $c(e)$, and two vertices $s$ and $t$, I want to find a path $P$ from $s$ to $t$ that maximizes the minimum edge capacity along the path, formally:
$$ \max_{P: s \to t} \min_{e \in P} c(e) $$
This differs from the shortest path problem, where I would instead minimize a sum of edge weights. Here, I care about maximizing the “bottleneck” capacity of the best available path.
Core Concepts
- Bottleneck edge: the edge with the smallest capacity along a given path, which determines that path’s overall throughput.
- Widest path: the path from source to destination whose bottleneck capacity is the largest among all possible paths.
- Capacity: the maximum flow or throughput an edge can support, analogous to bandwidth or pipe diameter.
- Maximum spanning tree connection: a key theoretical fact I rely on is that the widest path between any two nodes in a graph is always contained within the graph’s maximum spanning tree.
How It Works
I generally use one of two approaches depending on whether I need a single path or all-pairs widest paths.
Modified Dijkstra approach (single source, single or all destinations):
- I initialize the bottleneck capacity of the source to infinity, and all other vertices to negative infinity (or zero, depending on convention).
- I use a priority queue ordered by bottleneck capacity, always extracting the vertex with the current highest known bottleneck value.
- For each neighboring edge, I compute the candidate bottleneck as the minimum of the current vertex’s bottleneck value and the edge’s capacity.
- If this candidate is larger than the neighbor’s currently recorded bottleneck, I update it and push the neighbor into the queue.
- I repeat until I reach the destination or process all vertices.
Maximum spanning tree approach (many queries on the same graph):
- I compute the maximum spanning tree of the graph, using Kruskal’s or Prim’s algorithm but always preferring higher-weight edges.
- For any query between two vertices $s$ and $t$, I find the unique path between them in this maximum spanning tree.
- The bottleneck capacity of that unique tree path is exactly the answer to the widest path query.
Working Principle
The reason the modified Dijkstra approach works is that I have simply swapped the combination operator from addition (used for total distance) to minimum (used for bottleneck), and swapped the comparison operator from minimize to maximize. Because Dijkstra’s algorithm’s correctness only depends on the combination operator being monotonic (adding or combining edges never improves a path’s overall value), and the minimum operator satisfies this same monotonic property, the greedy priority-queue-based approach remains provably correct. The maximum spanning tree connection works because in a maximum spanning tree, I have already resolved the tradeoffs optimally across the entire graph: any path outside the tree between two vertices can be shown to have a bottleneck capacity no better than the tree path, due to the same cut property reasoning I use for standard spanning trees.
Mathematical Foundation
I define the bottleneck value of a path $P = (e_1, e_2, \ldots, e_k)$ as:
$$ B(P) = \min_{i=1}^{k} c(e_i) $$
and I want to find:
$$ P^* = \arg\max_{P: s \to t} B(P) $$
For the modified Dijkstra relaxation step, when I consider extending a path ending at vertex $u$ with bottleneck value $B(u)$ across edge $(u, v)$ with capacity $c(u,v)$, I update:
$$ B(v) = \max\big(B(v),\ \min(B(u),\ c(u,v))\big) $$
This relaxation rule replaces the usual shortest-path relaxation $d(v) = \min(d(v), d(u) + w(u,v))$.
Diagrams
flowchart TD
A[Initialize source bottleneck = infinity, others = -infinity] --> B[Push source into priority queue]
B --> C[Extract vertex with maximum known bottleneck]
C --> D[For each neighbor, compute min of current bottleneck and edge capacity]
D --> E{Is candidate better than neighbor's recorded bottleneck?}
E -- Yes --> F[Update neighbor bottleneck and push into queue]
E -- No --> G[Skip]
F --> H{Queue empty or destination reached?}
G --> H
H -- No --> C
H -- Yes --> I[Return bottleneck capacity and path]
Pseudocode
function WIDEST_PATH(G, source, target):
bottleneck = map with all vertices set to -infinity
bottleneck[source] = infinity
previous = empty map
priority_queue = {(source, infinity)}
while priority_queue not empty:
(u, b_u) = EXTRACT_MAX(priority_queue)
if u == target:
break
for each edge (u, v) with capacity c in G:
candidate = min(b_u, c)
if candidate > bottleneck[v]:
bottleneck[v] = candidate
previous[v] = u
INSERT(priority_queue, (v, candidate))
return bottleneck[target], RECONSTRUCT_PATH(previous, target)
Step-by-Step Example
Using the graph in the diagram: S-A(10), S-B(4), A-T(6), B-T(8), A-B(3), I want the widest path from S to T.
- Initialize: bottleneck(S) = infinity, all others = -infinity. Queue: {S}.
- Extract S. Relax S-A: candidate = min(infinity, 10) = 10, better than -infinity, so bottleneck(A) = 10. Relax S-B: candidate = min(infinity, 4) = 4, so bottleneck(B) = 4.
- Extract A (bottleneck 10, the largest in queue). Relax A-T: candidate = min(10, 6) = 6, better than -infinity, so bottleneck(T) = 6. Relax A-B: candidate = min(10, 3) = 3, but bottleneck(B) is already 4, so I skip since 3 < 4.
- Extract B (bottleneck 4). Relax B-T: candidate = min(4, 8) = 4, but bottleneck(T) is already 6, so I skip since 4 < 6.
- Extract T (bottleneck 6). Target reached.
- The widest path from S to T is S-A-T, with a bottleneck capacity of 6.
Time Complexity
Using a binary heap priority queue, this modified Dijkstra approach costs $O((V + E) \log V)$, exactly matching standard Dijkstra’s complexity, since I only changed the comparison and combination operators, not the overall algorithmic structure. If I use the maximum spanning tree approach for repeated queries, building the tree costs $O(E \log V)$ once, and then each individual query costs $O(V)$ using a simple tree traversal, or $O(\log V)$ with more advanced techniques like binary lifting for lowest common ancestor queries.
Space Complexity
For the modified Dijkstra approach, I need $O(V + E)$ space for the graph, plus $O(V)$ for the bottleneck values, previous-vertex tracking, and the priority queue. For the maximum spanning tree approach, I need an additional $O(V)$ space to store the tree structure itself, plus $O(V \log V)$ if I precompute binary lifting tables for fast repeated queries.
Correctness Analysis
The correctness proof mirrors Dijkstra’s original proof almost exactly. I rely on the fact that once I extract a vertex from the priority queue with the current maximum bottleneck value, that value can never be improved later, because any future path reaching this vertex would have to pass through a vertex with an even lower bottleneck value already in the queue, and the minimum operator ensures combining with a smaller value can never increase the bottleneck. This greedy-extraction invariant, which held for Dijkstra’s additive shortest paths, transfers directly to the minimum-maximum widest path formulation because both operators (addition and minimum) share the necessary monotonicity property for the greedy approach to remain valid.
Advantages
- It reuses the exact same algorithmic machinery as Dijkstra’s algorithm, so it is easy for me to implement if I already know shortest path algorithms.
- The maximum spanning tree approach allows extremely fast repeated queries after a one-time preprocessing cost.
- It has clear, well-understood correctness guarantees.
- It applies naturally to real capacity-constrained systems like networks and pipelines.
Disadvantages
- Like Dijkstra’s algorithm, the basic version does not handle negative capacities meaningfully, since capacities are typically non-negative physical quantities.
- It only finds the single widest path, not the full maximum flow between two nodes, which is a related but distinct problem requiring different algorithms like Ford-Fulkerson.
- Dense graphs with many high-capacity alternate routes can still require exploring a large portion of the graph before converging.
Applications
I use this kind of algorithm when analyzing network bandwidth planning, where I want to know the maximum sustained throughput achievable along a given communication route. It also applies to logistics and supply chain routing, where the “weakest link” (smallest capacity vehicle, road, or pipe) constrains the overall shipment size, in electrical grid capacity planning, and in financial applications like finding the maximum amount transferable through a chain of currency exchange or credit relationships limited by individual transaction caps.
Implementation in C
#include <stdio.h>
#include <limits.h>
#define MAXV 100
#define NEG_INF INT_MIN
int graph[MAXV][MAXV]; /* capacity matrix, 0 if no edge */
int n;
/* Modified Dijkstra: instead of minimizing sum of weights, I maximize
the minimum edge capacity (bottleneck) along the path. */
int widest_path(int source, int target, int prev[]) {
int bottleneck[MAXV];
int visited[MAXV] = {0};
for (int i = 0; i < n; i++) { bottleneck[i] = NEG_INF; prev[i] = -1; }
bottleneck[source] = INT_MAX;
for (int count = 0; count < n; count++) {
int u = -1, best = NEG_INF;
for (int i = 0; i < n; i++)
if (!visited[i] && bottleneck[i] > best) { best = bottleneck[i]; u = i; }
if (u == -1) break;
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (graph[u][v] > 0 && !visited[v]) {
int candidate = (bottleneck[u] < graph[u][v]) ? bottleneck[u] : graph[u][v];
if (candidate > bottleneck[v]) {
bottleneck[v] = candidate;
prev[v] = u;
}
}
}
}
return bottleneck[target];
}
void print_path(int prev[], int target) {
if (prev[target] != -1) print_path(prev, prev[target]);
printf("%d ", target);
}
int main() {
n = 4; /* S=0, A=1, B=2, T=3 */
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
graph[i][j] = 0;
graph[0][1] = graph[1][0] = 10; /* S-A */
graph[0][2] = graph[2][0] = 4; /* S-B */
graph[1][3] = graph[3][1] = 6; /* A-T */
graph[2][3] = graph[3][2] = 8; /* B-T */
graph[1][2] = graph[2][1] = 3; /* A-B */
int prev[MAXV];
int result = widest_path(0, 3, prev);
printf("Maximum capacity from S to T: %d\n", result);
printf("Path: ");
print_path(prev, 3);
printf("\n");
return 0;
}
Sample Input and Output
Using the same graph from my step-by-step example, running this program gives:
Maximum capacity from S to T: 6
Path: 0 1 3
This confirms the path S-A-T (vertices 0-1-3) with bottleneck capacity 6, matching my manual calculation.
Optimization Techniques
I replace the simple array-based minimum extraction in my C implementation with a binary heap or Fibonacci heap when working with large sparse graphs, since the naive $O(V^2)$ scan for the maximum bottleneck vertex becomes a bottleneck itself on large graphs. When I need repeated widest-path queries between many pairs of vertices on a static graph, I precompute the maximum spanning tree once and use binary lifting or sparse table techniques to answer each query in $O(\log V)$ time instead of rerunning Dijkstra every time.
Common Mistakes
I have seen people accidentally reuse standard Dijkstra’s relaxation logic (addition and minimization) without correctly swapping in the minimum-and-maximization logic required here, which silently produces a shortest path instead of a widest path. Another common mistake is initializing bottleneck values to zero instead of negative infinity, which can incorrectly treat zero-capacity paths as valid options in graphs where legitimate capacities could theoretically be zero or where unreachable vertices need clear distinction from reachable ones with low capacity.
Further Reading
- Pollack, M., “The maximum capacity through a network,” Operations Research, 1960.
- Hu, T.C., “The maximum capacity route problem,” Operations Research, 1961.
- Ford, L.R., Fulkerson, D.R., “Flows in Networks,” Princeton University Press, 1962. https://press.princeton.edu/books/paperback/9780691146676/flows-in-networks
- Wikipedia overview: https://en.wikipedia.org/wiki/Widest_path_problem
- Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., “Introduction to Algorithms,” MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
