Minimum Bottleneck Paths: Why the MST Path Minimises the Maximum Edge

Bottleneck cost versus path length

Take an undirected graph G = (V, E) with edge weights w. For a path P, define bottleneck(P) = max_e∈P w(e). The bottleneck distance b(u, v) is the minimum of bottleneck(P) over all u–v paths. The definition only changes the aggregation, max in place of sum, but that change has large consequences.

The most useful way to think about b is through thresholds. Let G_t be the subgraph that keeps only edges with weight ≤ t. Then b(u, v) is the smallest t at which u and v land in the same connected component of G_t. Picture water slowly flooding a landscape. Edges are submerged ridges, and two valleys become connected the moment the water passes the lowest ridge between them. Three facts follow from this view:

• Only the order of the weights matters. Replace every weight by its rank, or apply any strictly increasing function, and every bottleneck path stays optimal. Shortest paths have no such property. This is why bottleneck answers are robust to how you scale a cost.
• b is an ultrametric. b(u, x) ≤ max(b(u, v), b(v, x)) for every v, which is stronger than the triangle inequality. Single-linkage clustering dendrograms are exactly this ultrametric.
• Answers are shared. When components merge at threshold t, every newly connected pair gets distance t, which is why one tree can answer all pairs.

The proof in one cut

Claim. Let T be any MST of a connected undirected graph G. For every pair u, v, the path P between them in T satisfies bottleneck(P) = b(u, v).

Proof. Let e = (a, b) be the heaviest edge on P, with weight W. Delete e from T. The tree falls into two components, S containing u and V−S containing v. Now take any u–v path Q in G. Since Q starts in S and ends outside it, Q must use at least one edge f that crosses the cut (S, V−S). Suppose w(f) < W. Then T − e + f is a spanning tree lighter than T, which contradicts T being minimum. So w(f) ≥ W, and therefore bottleneck(Q) ≥ w(f) ≥ W = bottleneck(P). Since Q was arbitrary, P is optimal. ∎

Ties do not break the argument, because every step uses ≥. Uniqueness of the MST is not needed either. Different MSTs can produce different tree paths, but they all return the same bottleneck value, because b(u, v) is a property of G and not of the tree.

There is a second view. Kruskal adds edge e of weight t exactly when the two sides first become connected in G_t, which is the threshold definition. So Kruskal computes bottleneck distances incrementally, and its tree records them.

Every MST is bottleneck-optimal, not the converse

A minimum bottleneck spanning tree (MBST) is a spanning tree whose heaviest edge is as light as possible. Every MST is an MBST: apply the proof above to the endpoints of the MST's heaviest edge. The converse is false, and the difference matters in practice.

Take three vertices 1, 2, 3 with edges 1–2 of weight 1, 2–3 of weight 5 and 1–3 of weight 5. Any spanning tree must use a weight-5 edge, so every spanning tree has bottleneck 5, and the tree {2–3, 1–3} is a valid MBST. Its path from 1 to 2 is 1–3–2 with bottleneck 5, but the true b(1, 2) is 1 through the direct edge. An MBST only guarantees the global maximum. It says nothing about the paths inside it.

So never use an MBST routine's paths for pairwise queries. Use a true MST from Kruskal, Prim or Borůvka.

Worked example on six vertices

Here are the ten edges sorted by weight, with what Kruskal does to each:

Query A→F. The tree path is A–B–C–D–F with weights 4, 2, 5 and 6, so the bottleneck is 6. You can check this from the threshold side. In G₅, F has no incident edge at all, because its edges weigh 6, 10 and 12, so no path can beat 6. Compare the ordinary shortest path. Dijkstra picks the direct A–F edge, with total 12 against 17 for the tree path, and that edge's bottleneck is 12, twice as bad. The two objectives really do choose different routes.

Query A→E. The tree path has bottleneck max(4, 2, 5, 3) = 5, while the tempting shortcut A–C–E has bottleneck 8.

One query, three algorithms

If you only need a few answers, you do not need the whole tree. Three approaches are worth knowing.

Threshold search. Sort the distinct weights, then binary search for the smallest t at which s and t are connected using only edges ≤ t. Each probe is one BFS or one union-find pass, so the total cost is O(m log m). The method is easy to get right and doubles as a test oracle.

Minimax Dijkstra. Run Dijkstra but relax with max instead of +. Dijkstra is correct for any path cost that never decreases when you extend a path, and max satisfies that. You get bottleneck distances from one source to every vertex in O(m log n).

import heapq

def minimax_from(source, adj):
    """adj[u] = [(v, w), ...]; returns best[v] = b(source, v), inf if unreachable."""
    best = {source: float("-inf")}           # empty path has no edge yet
    heap = [(float("-inf"), source)]
    done = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue
        done.add(u)
        for v, w in adj[u]:
            nd = max(d, w)                     # the only change from Dijkstra
            if nd < best.get(v, float("inf")):
                best[v] = nd
                heapq.heappush(heap, (nd, v))
    return best

Linear time by median splitting. This is Camerini's idea, originally for MBSTs, adapted to a single s–t pair. Find the median edge weight M with linear-time selection. If s and t are connected using the light half, the heavy half is irrelevant, so keep only the light edges and recurse. If they are not connected, contract each light component to one super-vertex, because crossing inside one is free below M, and recurse on the heavy edges between super-vertices. Each round discards half the edges, so the total work is m + m/2 + m/4 + … = O(m).

bottleneck(G, s, t):
    if G has one edge on an s-t path: return its weight
    M      = median weight of E(G)                  # linear-time select
    light  = {e : w(e) <= M}
    if connected(s, t, light):
        return bottleneck((V, light), s, t)
    comp   = components(V, light)                   # BFS, O(m)
    G'     = contract G by comp, keep edges w > M, drop self-loops
    return bottleneck(G', comp[s], comp[t])

In practice the Dijkstra variant usually wins on constant factors.

Many queries with path maxima

For many queries on a static graph, build the MST once and answer each query with a path-maximum lookup. Binary lifting stores, for every vertex, its 2^k-th ancestor and the heaviest edge on the way there. A query climbs both endpoints to their lowest common ancestor and takes the maximum of the edges it passes.

from collections import deque

def build(n, edges):                      # edges: [(w, u, v)], vertices 0..n-1
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    adj = [[] for _ in range(n)]
    for w, u, v in sorted(edges):         # Kruskal
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            adj[u].append((v, w)); adj[v].append((u, w))
    LOG = max(1, n.bit_length())
    up  = [[-1] * n for _ in range(LOG)]
    mx  = [[float("-inf")] * n for _ in range(LOG)]
    depth, seen = [0] * n, [False] * n
    for root in range(n):                 # one BFS per tree of the forest
        if seen[root]:
            continue
        seen[root], up[0][root] = True, root
        q = deque([root])
        while q:
            u = q.popleft()
            for v, w in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    up[0][v], mx[0][v], depth[v] = u, w, depth[u] + 1
                    q.append(v)
    for k in range(1, LOG):
        for v in range(n):
            a = up[k - 1][v]
            up[k][v] = up[k - 1][a]
            mx[k][v] = max(mx[k - 1][v], mx[k - 1][a])
    return find, up, mx, depth, LOG

def query(u, v, find, up, mx, depth, LOG):
    if find(u) != find(v):
        return float("inf")                # disconnected: no path at all
    best = float("-inf")
    if depth[u] < depth[v]:
        u, v = v, u
    for k in reversed(range(LOG)):         # lift u to v's depth
        if depth[u] - (1 << k) >= depth[v]:
            best = max(best, mx[k][u]); u = up[k][u]
    if u == v:
        return best
    for k in reversed(range(LOG)):         # lift both to just below the LCA
        if up[k][u] != up[k][v]:
            best = max(best, mx[k][u], mx[k][v])
            u, v = up[k][u], up[k][v]
    return max(best, mx[0][u], mx[0][v])

Preprocessing is O(m log m + n log n), and each query costs O(log n). Alternatively, a Kruskal reconstruction tree turns each merge into a node labelled with its weight, so a query becomes a plain LCA lookup. If all queries are known up front, resolve each one during Kruskal at the moment its endpoints first share a component.

Widest paths and directed graphs

Widest paths. Flip the objective to maximise the minimum edge, as in bandwidth routing or keeping maximum clearance from obstacles. Build a maximum spanning tree, by sorting descending or negating the weights, and the same proof shows its paths are maximin-optimal. Minimax Dijkstra flips the same way: use a max-heap and relax with min.

Directed graphs break the shortcut. The cut proof relies on symmetry: any path from u to v crosses the cut through some edge, and that edge could replace e in the tree. With directed edges, a crossing edge can point the wrong way, and reachability is not symmetric, so no spanning structure can encode all pairs. A minimum arborescence (Chu–Liu/Edmonds) minimises the sum of weights out of one root and does not preserve path maxima. For directed graphs, run minimax Dijkstra once per source you need, or use threshold search with directed reachability.

Where bottleneck paths show up

• Single-linkage clustering. Cutting the k−1 heaviest MST edges gives the k-clustering that maximises the minimum gap between clusters. Each cut height is a bottleneck distance.
• Watersheds and flooding. On a terrain grid with edge weight max(height(u), height(v)), b(u, v) is the lowest water level at which u and v join. That is the spill elevation used in hydrology and in morphological image segmentation.
• Capacity planning. On a network weighted by utilisation, the minimax route between two sites shows which single link you must upgrade first to relieve that pair.

Failure modes

• Using an MBST, or a shortest-path tree. Neither one's paths are bottleneck-optimal. Only an MST gives the all-pairs guarantee, as the triangle counterexample shows.
• Forgetting disconnection. Kruskal on a disconnected graph produces a forest. Return infinity for cross-component queries instead of letting the LCA climb run off the root.
• Applying the tree to a digraph. Symmetrising a directed graph and taking its MST returns answers that look plausible and are wrong. Use the directed algorithms.
• Floating-point ties. Near-equal weights can change which route is reported between runs. Quantise weights if the route must be stable.
• Dynamic graphs. Inserting an edge (u, v, w) changes the MST only if w is less than the current path maximum between u and v. Then you swap out that maximum edge, which needs a link-cut tree or a rebuild. Deletions are harder still. Batch them and rebuild.

Testing an implementation

Bottleneck code is easy to test because a slow oracle is trivial to write: for each query, run threshold search with union-find over the sorted edges. Generate random graphs with small integer weights, since many ties exercise the ≥ cases, plus some disconnected ones. Assert that the binary-lifting answer, the minimax Dijkstra answer and the oracle agree on every pair, and check the ultrametric inequality on random triples.

What to do next

1. Decide whether your graph is directed. If it is, use minimax Dijkstra per source and stop here.
2. Build a true MST with Kruskal, not an MBST, and keep the union-find so you can detect disconnected pairs.
3. For a few queries, run minimax Dijkstra from each source. For many, add binary lifting with path maxima, or a Kruskal reconstruction tree.
4. Write the threshold-search oracle first and property-test against it on tie-heavy random graphs.
5. If the objective is maximin bandwidth or clearance, switch to a maximum spanning tree and rerun the same tests.
6. Look for single-linkage clustering or watershed problems hiding in your workload and reuse the same tree for them.

Related reading on this site: Kruskal's algorithm, animated, Prim's algorithm, union-find, LCA by binary lifting, Dijkstra in depth and the second-best MST, which reuses the same path-maximum queries.