Shortest Paths and Minimum Spanning Trees

12.1Single-source shortest paths

BFS is correct for unweighted graphs because it processes vertices by number of edges from the source. It cannot guarantee that the front vertex of its queue has the smallest weighted distance.

Relaxing an edge

For the slide example, d(Diamond)=10, d(Ruby)=15, and w(Diamond,Ruby)=2. Relaxation changes d(Ruby) to min(15,10+2)=12. With array-held estimates, the update itself is O(1).

for each vertex v in G.V:
    v.d = ∞
    v.π = NIL
s.d = 0

12.2Dijkstra’s algorithm

Dijkstra computes shortest paths from one source by repeatedly choosing the unsettled vertex with the smallest tentative distance. It is a greedy algorithm: once that vertex is extracted, its estimate becomes final. This conclusion is valid only when every reachable edge has a non-negative weight.

1. Initialize d[s]=0, all other distances to ∞, and every predecessor to NIL.
2. Extract the unsettled vertex u with minimum d[u]; its distance is now settled.
3. Relax every outgoing edge (u,v). If d[u]+w(u,v) is smaller, update both d[v] and π[v].
4. Continue until the queue is empty, or stop early after the desired destination is extracted.

def dijkstra(G, w, s):
    initialize_single_source(G, s)       # O(V)
    S = set()
    Q = min_heap(G.vertices)             # O(V)
    while Q:
        u = extract_min(Q)               # V times, O(log V) each
        S.add(u)
        for v in G.adj[u]:
            if relax(u, v, w):
                decrease_key(Q, v, v.d)  # O(log V)

Dijkstra’s algorithm — implementation guide

Choose the graph representation and priority structure according to graph density. In this comparison, a min-heap means a binary min-heap supporting an efficient decrease-key operation.

12.3Negative edges and Dijkstra’s limitation

A negative edge does not automatically make a particular Dijkstra run fail, but Dijkstra has no correctness guarantee when negative weights are allowed. A later negative edge can improve a vertex already declared final.

12.4Bellman–Ford algorithm

Bellman–Ford solves single-source shortest paths even when some edges are negative. Instead of making a greedy final decision, it repeatedly propagates better estimates across every edge. A shortest simple path contains at most |V|−1 edges, so |V|−1 complete passes are sufficient when no reachable negative-weight cycle exists.

def bellman_ford(G, w, s):
    initialize_single_source(G, s)
    for _ in range(|V| - 1):
        for (u, v) in G.edges:
            relax(u, v, w)
    for (u, v) in G.edges:
        if d[v] > d[u] + w(u, v):
            return False  # reachable negative cycle
    return True

12.5Shortest-path variants and unweighted graphs

Unweighted shortest paths: use BFS

When every edge has equal cost, minimizing total cost is exactly the same as minimizing the number of edges. BFS uses a FIFO queue to explore vertices in layers 0, 1, 2, … from the source.

12.6Minimum spanning trees

• Every spanning tree has exactly |V|−1 edges.
• An MST may not be unique. If all edge weights are distinct, the MST is unique.
• For a disconnected graph, Prim and Kruskal produce a minimum spanning forest, not one spanning tree.
• Prim and Kruskal both rely on the cut property: a lightest edge crossing a cut that respects the partial solution is safe to add.

12.7Prim’s algorithm

Prim grows a single tree from an arbitrary root. For each vertex outside the tree, key[v] is the lightest edge currently known from the tree to that vertex, and π[v] is the tree vertex that provides that edge.

def mst_prim(G, w, r):
    for u in G.V: u.key, u.parent = ∞, NIL
    r.key = 0
    Q = min_heap(G.V)
    while Q:
        u = extract_min(Q)
        for v in G.adj[u]:
            if v in Q and w(u,v) < v.key:
                v.parent = u
                v.key = w(u,v)
                decrease_key(Q, v, v.key)

12.8Kruskal’s algorithm

Kruskal begins with one component per vertex, sorts all edges by nondecreasing weight, and accepts an edge exactly when its endpoints are in different components. The accepted edge merges those components; an edge whose endpoints already share a component is rejected because it would create a cycle.

def kruskal(G):
    A = []
    make_set(v) for each v in G.V
    for (u, v, w) in sorted(G.edges, key=weight):
        if find_set(u) != find_set(v):
            A.append((u, v, w))
            union(u, v)
    return A

12.9Questions and exercises

Exact directed-graph exercises from the slides

Dijkstra versus Prim

Both may use a min-priority queue and grow outward from a vertex. Dijkstra’s key is the total distance from the source; Prim’s key is the weight of one cheapest edge joining a vertex to the current tree. Prim may start at any vertex.