Shortest Paths & Union-Find: Weighted Roads and Cheap Networks

What you'll learn

• How weights change the shortest-path question, and the single operation behind every shortest-path algorithm: relaxing an edge
• Dijkstra's algorithm with a heap: why its greedy choice is safe, how to rebuild the route, and why it costs O((V + E) log V)
• Why negative edges break Dijkstra, and how Bellman-Ford copes with them and detects negative cycles
• The Union-Find (disjoint set) structure, with union by size and path compression
• Minimum spanning trees and Kruskal's algorithm, built on Union-Find
• You will write: Dijkstra, Bellman-Ford with cycle detection, and Kruskal

The GPS and the cable company

In Trees & Graphs, BFS found the fewest moves through a maze, because every step cost the same. A road map is different. A route of five short city streets can be faster than two long country roads, so each road (edge) carries a weight: minutes, kilometres or money. The question becomes: which route has the smallest total weight? Your GPS answers it on a graph with millions of junctions, and the internet answers it continuously: in the OSPF routing protocol (RFC 2328) every router builds a shortest-path tree of the network with Dijkstra's algorithm, while RIP (RFC 2453) is a distance-vector protocol built on the Bellman-Ford idea.

A cable company asks a different question. It must connect every town to the network, and laying cable between two towns has a cost. It does not care about the shortest route from one town to another; it wants the cheapest set of cables that keeps everything connected. That is a minimum spanning tree, and the tool that makes it fast is Union-Find, a structure that answers "are these two already connected?" almost instantly.

Weighted graphs and Dijkstra's algorithm

Store a weighted graph as an adjacency list of (neighbour, weight) pairs. Every shortest-path algorithm keeps dist[v], the best distance from the source found so far (0 for the source, infinity for the rest), and improves it with one operation, relaxing an edge u -> v of weight w:

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w        # going through u is better
    parent[v] = u                # remember how we got here, to rebuild the route

The algorithms differ only in the order in which they relax edges. BFS's order is wrong as soon as weights differ:

A --5--> C
A --1--> B --1--> C

fewest edges:   A -> C        (1 edge, cost 5)
cheapest:       A -> B -> C   (2 edges, cost 2)

Dijkstra's algorithm (Edsger Dijkstra, 1959) works when no weight is negative. Repeatedly take the vertex with the smallest tentative distance that is not final yet, declare its distance final, and relax its outgoing edges. A min-heap hands you that vertex. Why may it be declared final? Any other route to it must leave the finished vertices at some unfinished vertex whose tentative distance is already at least as large, and edges that cannot be negative never make a route shorter.

Library heaps cannot lower a priority in place, so use lazy deletion: push (new distance, v) every time dist[v] improves, and when you pop an entry whose distance is larger than dist[v], it is outdated: skip it. With weights that are never negative, each vertex passes this check exactly once, at its final distance.

import heapq

def dijkstra(graph, source):
    dist = {v: float("inf") for v in graph}
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                     # outdated entry
        for v, w in graph[u]:
            if d + w < dist[v]:          # relax u -> v
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

S --4--> A,  S --1--> B,  B --2--> A,  A --1--> C,  B --5--> C

pop S (0)   relax: A = 4, B = 1
pop B (1)   relax: A = 1 + 2 = 3 (better than 4), C = 1 + 5 = 6
pop A (3)   relax: C = 3 + 1 = 4 (better than 6)
pop A (4)   outdated (dist[A] is 3): skip
pop C (4)   final.  Distances: S 0, B 1, A 3, C 4.  Route to C: S -> B -> A -> C

Every improvement pushes one entry, so the heap holds O(E) entries and the algorithm runs in O((V + E) log V). To print a route, follow parent back from the target and reverse the list.

Negative edges and Bellman-Ford

Dijkstra's promise "the smallest tentative distance is final" relies on edges never being negative. Break that rule and the promise fails:

        2           1
   A ------> B ------> D
    \        ^
   3 \       | -2
      \----> C

pop A (0)   relax: B = 2, C = 3
pop B (2)   B "final" at 2;  relax: D = 3
pop C (3)   relax C -> B: 3 - 2 = 1 < 2
real:       B = 1 (A -> C -> B),  D = 2 (A -> C -> B -> D)

The argument breaks the moment a popped vertex is treated as final: B was popped at 2, but a later edge of weight -2 makes it 1. A version that marks popped vertices as done and never touches them again keeps B = 2 and D = 3, both wrong. The lazy code above has no such mark: when C -> B lowers B, it pushes B again, expands it a second time and fixes D. It returns correct distances as long as no negative cycle is reachable, but it is no longer the algorithm whose cost you know: a vertex can be expanded many times, exponentially many in the worst case, and if a negative cycle is reachable the loop never ends. Negative weights need an algorithm built for them.

Negative weights are not exotic: a step that earns a refund or a bonus, or currency exchange, where taking -log(rate) as the weight turns "multiply the rates" into "add the weights", so a profitable loop of trades (arbitrage) becomes a cycle of negative total weight.

Bellman-Ford (Richard Bellman and Lester Ford, 1950s) makes no assumption about the order. It simply relaxes every edge, V - 1 times:

dist = {v: float("inf") for v in graph}
dist[source] = 0
for _ in range(V - 1):
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

Why V - 1 rounds? A shortest path that does not repeat a vertex has at most V - 1 edges. After round 1, every vertex whose shortest path has 1 edge is correct; after round k, every vertex whose shortest path has at most k edges is correct. You can stop early when a round changes nothing. The cost is O(V x E): slower than Dijkstra, but it accepts negative weights.

Negative cycles. If a cycle has negative total weight and the source can reach it, you can go around it forever and every loop makes the route cheaper: the shortest distance is not defined. Bellman-Ford detects this with one extra round: if any edge can still be relaxed after V - 1 rounds, a negative cycle is reachable. (A negative cycle the source cannot reach does no harm; skip edges that start at an unreachable vertex.) Distance-vector routing protocols are distributed Bellman-Ford: routers repeatedly send their distance tables to their neighbours, and RIP caps a route at 15 hops, using a metric of 16 to mean "unreachable".

Which tool when? All steps cost the same: BFS. Weights 0 or more: Dijkstra. Negative weights, or you must detect negative cycles: Bellman-Ford. (For all pairs on a small graph, Floyd-Warshall runs in O(V³).)

Union-Find: who is connected to whom?

Links keep appearing (friendships, cables, merged accounts) and you must answer, at any moment, "are x and y in the same group?". Running a BFS for each question costs O(V + E). Union-Find (a disjoint-set structure) answers in almost constant time.

The idea: every group is a small tree, stored in a parent array; the root of the tree represents the group.

• find(x): follow parents from x up to the root and return it. Two elements are in the same group exactly when find returns the same root.
• union(a, b): find both roots; if they differ, hang one root under the other.

Two small tricks make the trees almost flat:

• Union by size: hang the smaller tree under the larger one. A tree can then only get one level deeper when its size at least doubles, so heights stay O(log n).
• Path compression: during find, point the nodes you pass closer to the root, so the next find is shorter. The one-line form below is called path halving.

parent = list(range(n))          # everyone starts alone
size = [1] * n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path halving: skip a level while climbing
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                    # already in the same group
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra                     # the smaller tree goes under the larger
    size[ra] += size[rb]
    return True

union(1, 2), union(3, 4):        1     3
                                 |     |          (a line joins a child to its parent)
                                 2     4
union(2, 4): roots 1 and 3       1
                                / \
                               2   3
                                   |
                                   4              find(4) then re-points 4 straight at 1

With both tricks, a sequence of operations costs O(α(n)) amortised per operation, where α is the inverse Ackermann function (Robert Tarjan proved the bound for full path compression in 1975, and Tarjan and Jan van Leeuwen showed in 1984 that path halving achieves it too). α(n) is at most 4 for any n you could ever store, so in practice it is constant time.

Minimum spanning trees with Kruskal

A spanning tree of a connected, undirected graph keeps all V vertices connected using exactly V - 1 edges and no cycle. A minimum spanning tree (MST) is one with the smallest total weight: the cheapest cable network, the cheapest set of roads that links every village. MSTs are also used for clustering and as a building block of approximation algorithms.

Kruskal's algorithm (Joseph Kruskal, 1956) is greedy:

1. Sort the edges by weight, lightest first.
2. For each edge (u, v, w): if find(u) != find(v), take it and union(u, v); otherwise skip it, because it would close a cycle.
3. Stop after V - 1 edges. If you run out of edges first, the graph is not connected and has no spanning tree.

edges sorted:  0-1 (1)  1-2 (2)  0-2 (3)  2-3 (4)  1-3 (5)

0-1 (1)   different groups -> take    {0,1} {2} {3}
1-2 (2)   different groups -> take    {0,1,2} {3}
0-2 (3)   same group       -> skip    (0 and 2 are already connected)
2-3 (4)   different groups -> take    {0,1,2,3}: V - 1 = 3 edges, done
total weight 1 + 2 + 4 = 7

Why is greedy safe here? The cut property: split the vertices into two sides in any way; the lightest edge crossing between the sides belongs to a minimum spanning tree (with equal weights, to at least one of them). When Kruskal takes an edge, every lighter edge has already been considered, so it is the lightest edge leaving the group of one of its ends. Negative weights are fine too: only the order of the weights matters.

Cost: sorting is O(E log E); the Union-Find work is nearly linear. Prim's algorithm is the alternative: grow one tree from a start vertex, always adding the cheapest edge that leaves it, with a heap, in O(E log V). Prim's idea is close to Dijkstra's, and Dijkstra's 1959 paper actually describes both problems.

Summary

• In a weighted graph the shortest route minimises the sum of weights, not the number of edges. Every algorithm improves dist[v] by relaxing edges; they differ in the order.
• Dijkstra (weights 0 or more) settles the closest unfinished vertex with a min-heap, skips outdated entries, and runs in O((V + E) log V). Keep parent to rebuild the route.
• Negative edges break Dijkstra's promise that a popped vertex is final. Bellman-Ford relaxes every edge V - 1 times in O(V x E), and an improvement in one extra pass reveals a reachable negative cycle.
• Union-Find answers "same group?" and merges groups in O(α(n)) amortised with union by size and path compression.
• Kruskal sorts the edges and takes every edge that joins two different groups; the result is a minimum spanning tree with V - 1 edges, or proof that the graph is disconnected.

Practice next: compute how long a signal takes to reach every node of a network (Dijkstra), find the cheapest flight with at most k stops (a Bellman-Ford variant), count groups of friends and find the one redundant cable with Union-Find, and implement Prim's algorithm with a heap. Next on the roadmap is Greedy & Backtracking: Dijkstra and Kruskal were greedy algorithms whose choices you proved safe.