Algorithms 2

Graph Definitions & Representation

A graph G = (V, E) is a set of vertices and a set of edges E ⊆ V × V. In a directed graph edges are ordered pairs (u, v); in an undirected graph E is symmetric. A weighted graph has a weight function w : E → ℝ. A graph is fully connected if E = V × V.

Special Graph Types

DAG

Directed Acyclic Graph — no directed cycles. Admits a topological ordering.

Tree

Connected undirected acyclic graph. Has exactly |V|−1 edges.

Forest

Undirected acyclic graph (disjoint union of trees).

Connected

Undirected graph where every pair of vertices has a path between them.

Representations

For an undirected graph with an adjacency matrix, only the upper (or lower) triangle needs to be stored because the matrix is symmetric. A weighted adjacency matrix stores the weight in each cell (or ∞ for missing edges).

Breadth-First Search (SSAD_HOPCOUNT)

Problem: single-source all-destinations unweighted shortest paths — find v.d = hop-distance δ(s, v) for every vertex.

Course notation: v.d for distance, v.π for predecessor, v.pending for "currently in queue". (Used interchangeably below with seen/come_from.)

def bfs(g, s):
    for v in g.vertices:
        v.d = ∞; v.π = NIL; v.pending = False
    s.d = 0; s.pending = True
    Q = Queue([s])
    while not Q.isempty():
        u = Q.popleft()                          # FIFO
        for v in u.neighbours:
            if not v.pending:
                v.d = u.d + 1;  v.π = u;  v.pending = True
                Q.pushright(v)

Correctness — three lemmas

Depth-First Search

Recursive Implementation

def dfs(g):
    for v in g.vertices: v.visited = False; v.π = NIL
    time = 0
    for v in g.vertices:
        if not v.visited: dfs_helper(v)

def dfs_helper(u):
    time += 1; u.discover_time = time; u.visited = True
    for v in u.neighbours:
        if not v.visited:
            v.π = u; dfs_helper(v)
    time += 1; u.finish_time = time

Stack-Based Equivalent

def dfs_iter(g, s):
    for v in g.vertices: v.seen = False
    stack = Stack([s]);  s.seen = True
    while not stack.isempty():
        u = stack.popright()
        for v in u.neighbours:
            if not v.seen: stack.pushright(v);  v.seen = True

Each vertex has a discover_time (when it is first entered — "grey") and a finish_time (when its recursion returns — "black"). Times are integers 1…2|V|.

Edge Classification & DFS Properties

DFS on G produces a depth-first forest. Every edge (u, v) ∈ E falls into exactly one of four classes:

Tree edge

(u, v) was used to discover v (so v.π = u).

Back edge

v is an ancestor of u in the DF-forest. (Undirected graphs: only tree + back edges exist.)

Forward edge

Non-tree edge to a descendant of u.

Cross edge

Any edge between vertices with no ancestor relation (possibly across DF-trees — only possible in directed graphs).

Useful Consequences

• An undirected graph has a cycle ⟺ DFS finds a back edge.
• On an undirected graph, DFS identifies connected components: one per top-level call to dfs_helper.
• On a directed acyclic graph, sorting vertices by descending finish time gives a valid topological ordering.

Strongly Connected Components

A strongly connected component (SCC) of a directed graph G is a maximal C ⊆ V such that every pair u, v ∈ C is mutually reachable.

Runs in Θ(V + E). Proof of correctness is in CLRS ch.22. (Not proved in lectures.)

Bellman-Ford Algorithm

Problem: Single-source shortest paths in a directed graph with arbitrary edge weights. Returns true + valid distances if no negative-weight cycle is reachable from s, else returns false.

Core subroutine — RELAX(u, v, w):

def RELAX(u, v, w):
    if v.d > u.d + w(u, v):
        v.d = u.d + w(u, v);  v.π = u

def BELLMAN-FORD(G, w, s):
    for v in G.V: v.d = ∞;  v.π = NIL
    s.d = 0
    for i = 1 to |V|−1:
        for (u, v) in G.E:
            RELAX(u, v, w)
    for (u, v) in G.E:
        if v.d > u.d + w(u, v): return False   # negative cycle
    return True

Correctness Sketch

Dijkstra vs Bellman-Ford

Single-Source Shortest Paths on a DAG

If G is a DAG, SSSP is solvable in Θ(V + E) — faster than both Bellman-Ford and Dijkstra, and handles arbitrary edge weights.

def DAG-SSSP(G, w, s):
    for v in G.V: v.d = ∞;  v.π = NIL
    s.d = 0
    order = TOPOLOGICAL-SORT(G)              # Θ(V + E)
    for u in order:
        for v in G.adj[u]:
            RELAX(u, v, w)                   # Θ(E) total

Because vertices are relaxed in topological order, any shortest path s ⤳ v is relaxed edge-by-edge in the correct sequence — so when we reach v, v.d is final.

Dijkstra's Algorithm

Problem: Single-source shortest paths in a directed graph with non-negative edge weights. Greedy algorithm exploiting the optimal-substructure property of shortest paths.

def DIJKSTRA(G, w, s):
    for v in G.V: v.d = ∞;  v.π = NIL
    s.d = 0
    S = ∅                                    # processed set (proof bookkeeping)
    Q = new PriorityQueue(G.V, key=v.d)
    while not Q.isempty():
        u = Q.extract-min()
        S = S ∪ {u}
        for v in G.adj[u]:
            RELAX(u, v, w)                   # triggers DECREASE-KEY when v.d drops

Running Time — dominated by priority queue

Dijkstra Correctness

Initialisation. S = ∅, vacuously true. Maintenance (proof by contradiction):

Termination. Q is empty ⟹ S = V ⟹ the invariant gives v.d = δ(s, v) for every vertex.

Floyd-Warshall — All-Pairs Shortest Paths via DP

Problem: All-Pairs Shortest Paths on an arbitrarily weighted directed graph with no negative cycles. Output: the |V| × |V| matrix D where D_ij = δ(i, j).

Optimal Substructure

For i, j ∈ V, consider a minimum-weight path p from i to j whose intermediate vertices lie in {1, 2, …, k}. Two cases:

• k is not an intermediate in p: p is also minimum-weight using intermediates in {1, …, k−1}.
• k is an intermediate: p decomposes as i ⤳_p₁ k ⤳_p₂ j, where p₁ and p₂ both have intermediates in {1, …, k−1} (each being a shortest path between its endpoints under that restriction).

Recurrence

def FLOYD-WARSHALL(G, w):
    D⁰ = w                                  # copy adjacency-weight matrix
    for k = 1 to |V|:
        let Dᵏ = new matrix
        for i = 1 to |V|:
            for j = 1 to |V|:
                Dᵏ[i][j] = min(Dk-1[i][j],  Dk-1[i][k] + Dk-1[k][j])
    return D|V|

Extensions

• Predecessor matrix Π. Maintain in parallel π_ij^(k) = predecessor of j on a minimum i ⤳ j path using {1, …, k}. When the min picks option 1, keep π_ij^(k−1); when it picks option 2, use π_kj^(k−1).
• Transitive closure. Run Floyd-Warshall with w(i, j) = 1 for edges in E; d_ij < ∞ ⟺ (i, j) is in the transitive closure E*. Or reinterpret (min, +) as (OR, AND) on booleans.

APSP via Matrix Multiplication

Redefine matrix multiplication with (+, ·) replaced by (min, +). Then M^(t)_ij = min_k{ W_ik + M^(t−1)_kj } represents "min-weight path from i to j using ≤ t edges".

Because any shortest path has ≤ |V|−1 edges, M^(|V|−1) is the APSP matrix. Using repeated squaring we compute this in O(V³ log V) — worse than Floyd-Warshall but a cleaner conceptual derivation.

Johnson's Algorithm

Problem: All-pairs shortest paths on a graph that may have negative edges but no negative cycles. Runs in O(V E + V² lg V) — asymptotically faster than Floyd-Warshall's O(V³) when E ∈ o(V²), i.e. on sparse graphs.

Key Strategies

Reweighting Trick

Define ŵ(u, v) = w(u, v) + h(u) − h(v) for some h : V → ℝ. Check each property:

• Cycle invariance. Around any cycle the h-terms telescope to zero, so a cycle has the same weight under ŵ and w. (In particular, ŵ has a negative cycle ⟺ w does.)
• Path invariance up to endpoints. For any path p = v₀ ⤳ v_k: ŵ(p) = w(p) + h(v₀) − h(v_k). Since the h-correction depends only on endpoints, p minimises ŵ ⟺ p minimises w.

Choosing h

Augment G by adding a new source s with zero-weight edges s → v for every v ∈ V. Run Bellman-Ford from s; set h(v) = δ(s, v). Then for every original edge (u, v): h(v) ≤ h(u) + w(u, v) (triangle inequality), so ŵ(u, v) = w(u, v) + h(u) − h(v) ≥ 0. ✓

Running Time

Bellman-Ford: O(VE). Reweighting: O(E). V Dijkstras with a Fibonacci heap: V · O(E + V lg V) = O(VE + V² lg V). Un-reweighting: O(V²). Total: O(VE + V² lg V).

Flow Networks

A flow network is a directed weighted graph G = (V, E) with two distinguished vertices — a source s and a sink t — and non-negative edge capacities c : E → ℝ≥0. We extend c(u, v) = 0 if (u, v) ∉ E.

Flows and Values

A flow f : V × V → ℝ satisfies:

• Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v) for all u, v ∈ V.
• Flow conservation: for every u ∈ V \ {s, t}, Σ_v f(v, u) = Σ_v f(u, v).

The value of a flow: |f| = Σ_v f(s, v) − Σ_v f(v, s). (The second term matters when we generalise to multi-source networks, where the residual graph may include edges into s.)

Modelling Tricks

• Multi-source / multi-sink: add a supersource S with edges S → s_i (capacity ∞) and a supersink T with edges t_j → T (capacity ∞). This reduces to single-source single-sink without loss of generality.
• Antiparallel pair: replace (u, v) with u → v' → v (new vertex v', same capacity on both new edges).

Ford-Fulkerson Method

Three ingredients: residual networks, augmenting paths, and cuts.

Residual Network G_f

Given a flow f on G, the residual network has residual capacities:

The no-antiparallel constraint on E ensures exactly one case applies. Note G_f itself may contain antiparallel edges.

Augmenting Paths

An augmenting path is any simple s⤳t path p in G_f. Its residual capacity c_f(p) = min over edges on p of c_f(u, v). Augmenting flow f by this p increases |f| by c_f(p) > 0 while preserving validity.

def FORD-FULKERSON(G, s, t):
    for (u, v) in G.E: f(u, v) = 0
    while ∃ augmenting path p in Gf:
        δ = cf(p)
        for (u, v) in p:
            if (u, v) ∈ G.E: f(u, v) += δ           # inc edge: push more
            else:            f(v, u) −= δ           # dec edge: cancel flow
    return f

Running Time

With integer capacities, each augmenting path increases |f| by ≥ 1, and finding one via BFS/DFS on G_f costs O(V + E) = O(E). Total: O(E · |f*|), where f* is the max flow value.

With irrational capacities, Ford-Fulkerson may not terminate (augmentations can shrink in a non-convergent series).

Edmonds-Karp

Always pick the shortest augmenting path (edge count), by BFS on G_f. Runs in O(V E²) independent of f*; always terminates.

Max-Flow Min-Cut Theorem

A cut (S, T) of a flow network is a partition V = S ∪ T with s ∈ S and t ∈ T. The net flow across the cut is f(S, T) = Σ_{u∈S, v∈T} f(u, v) − Σ_{u∈S, v∈T} f(v, u), and by flow conservation f(S, T) = |f|. The capacity is c(S, T) = Σ_{u∈S, v∈T} c(u, v) — only forward edges S→T are counted.

Proof Structure: 1 ⇒ 2, 2 ⇒ 3, 3 ⇒ 1

Matchings in Bipartite Graphs

Given an undirected graph G = (V, E), a matching M ⊆ E is a set of edges with no shared endpoints. A vertex is matched if some edge of M is incident to it. We want a matching of maximum cardinality.

A bipartite graph has V = V₁ ∪ V₂ with E ⊆ V₁ × V₂ (every edge crosses between the parts). Classic application: pairing students to rooms in the housing ballot.

Approach 1: Translation to Max-Flow

1. Add source s, edges s → v (capacity 1) for each v ∈ V₁.
2. Add sink t, edges v → t (capacity 1) for each v ∈ V₂.
3. Direct each original edge V₁ → V₂, capacity 1.
4. Run Ford-Fulkerson. By the Integrality Theorem, integer capacities give an integer max flow, so every edge has flow 0 or 1.
5. Edges with flow 1 form a maximum matching.

Why This Works (both directions)

Therefore max flow = max matching. Running time O(V E) with Ford-Fulkerson (f* ≤ |V|/2 ≤ V).

Approach 2: Direct Augmenting Paths

An alternating path w.r.t. matching M is a path whose edges alternate "∉M, ∈M, ∉M, …". An augmenting path is an alternating path from an unmatched vertex in V₁ to an unmatched vertex in V₂. Flipping its membership (M ⊕ p) increases |M| by 1.

def MAXIMUM-MATCHING(G):
    M = ∅
    while ∃ augmenting path p for M:
        M = M ⊕ p
    return M

Finding an augmenting path is a modified BFS/DFS costing O(V + E) = O(E), and the algorithm does ≤ V/2 augmentations, giving O(V E).

Hopcroft-Karp

Finds all vertex-disjoint shortest augmenting paths in one pass and augments along all of them simultaneously. Analysis shows ≤ √V iterations suffice, giving O(E √V). (Proof is non-examinable.)

Minimum Spanning Trees — Safe Edges

A spanning tree of a connected undirected graph G is an acyclic subset T ⊆ E that connects all |V| vertices (hence |T| = |V|−1). A minimum spanning tree (MST) has minimum total weight w(T). MSTs are not necessarily unique.

Vocabulary

cut (S, V\S)

Partition of V.

edge crosses cut

One endpoint in S, the other in V\S.

cut respects A

No edge in A crosses the cut.

light edge

An edge crossing the cut with minimum weight among crossing edges (not necessarily unique).

safe edge for A

An edge e such that A ∪ {e} is still contained in some MST.

Both MST algorithms build A ⊆ E greedily, maintaining the invariant "A ⊆ some MST T" and adding safe edges until |A| = |V|−1.

Kruskal's Algorithm

Grow a forest of trees by repeatedly adding the lightest edge that connects two distinct trees (uses the corollary).

def MST-KRUSKAL(G, w):
    A = ∅
    S = new DisjointSet;  for v in G.V: MAKE-SET(S, v)
    edges = SORT(G.E, by weight, ascending)      # O(E lg V)
    for (u, v) in edges:
        if not IN-SAME-SET(S, u, v):
            A = A ∪ {(u, v)}
            UNION(S, u, v)
    return A

Running time: O(E lg V) — dominated by the sort. Disjoint-set operations (with path compression + union by rank) are effectively O(1) amortised, contributing only O((V + E) α(V)).

Application — Hierarchical Clustering

Kruskal's intermediate forests form a dendrogram: a classification tree with join heights reflecting merge weights. Used in image segmentation, bioinformatics, and exploratory data analysis.

Prim's Algorithm

Grow a single tree from an arbitrary root r, always adding the lightest edge crossing the "tree vs. rest" cut (directly applies the Safe Edge Theorem).

def MST-PRIM(G, w, r):
    Q = new PriorityQueue
    for v in G.V:
        v.key = ∞;  v.π = NIL;  Q.insert(v)
    Q.decrease-key(r, 0)
    while not Q.isempty():
        u = Q.extract-min()
        for v in G.adj[u]:
            if v ∈ Q and w(u, v) < v.key:
                v.π = u;  v.key = w(u, v)
                Q.decrease-key(v, v.key)

Differences from Dijkstra: v.key stores the weight of the lightest edge connecting v to the tree (not a cumulative path distance). The MST is {(v, v.π) : v ≠ r}.

Running time with a Fibonacci heap: |V| INSERTs and |V| EXTRACT-MINs cost O(V lg V); |E| DECREASE-KEYs cost O(E) amortised. Membership in Q is tracked with a bit vector in O(1). Total: O(E + V lg V). With a binary heap: O(E lg V).

Topological Sort

Problem: Given a DAG, return a total ordering of vertices such that every edge v₁ → v₂ has v₁ before v₂.

Why DAGs only? A cycle makes a total order impossible — each vertex on the cycle would need to precede itself.

def TOPOLOGICAL-SORT(G):
    for v in G.V: v.colour = 'white'
    totalorder = []
    for v in G.V:
        if v.colour == 'white': visit(v, totalorder)
    return totalorder

def visit(v, totalorder):
    v.colour = 'grey'                    # currently on the DFS stack
    for w in v.neighbours:
        if w.colour == 'white': visit(w, totalorder)
    v.colour = 'black';  totalorder.prepend(v)

Equivalent to: run DFS, then list vertices in descending finish time. Running time Θ(V + E).

Correctness

The colours are a conceptual device for the proof and are not actually tracked at runtime (the visited flag suffices).

Amortised Analysis

For algorithms, a worst-case per-operation bound is usually tight enough. For data structures, the worst case for a sequence of operations can be much tighter than (operations) × (worst single-operation cost). Three standard techniques:

1. Aggregate analysis — bound the total cost of a sequence directly.
2. Accounting method — assign "charges" that may exceed actual cost, with the excess stored as credit for later.
3. Potential method — track a whole-data-structure potential Φ and let ΔΦ mediate between true and amortised cost.

Aggregate Analysis

Bound the total cost c₁ + c₂ + ⋯ + c_m directly; the amortised cost is the average (total / m).

Example — Dynamic Array (doubling)

Start with capacity 16; on overflow, allocate 2× and copy. Starting from an array of 16 items and doing N = 2^k inserts, the total cost of the sequence is:

16 + (16+1) + 15 + (32+1) + 31 + (64+1) + 63 + ⋯ ∈ O(N)

Dividing by N gives amortised cost O(1) per insert. (This is the result we assumed for Stack push in Algorithms 1.)

Example — Binomial Heap Insertions

A single worst-case insertion merges up to ⌊lg N⌋ trees, costing Ω(lg N); but after such a costly insert the structure is "clean" and the next few inserts are cheap. Across N inserts starting from empty, total cost is O(N) (not O(N lg N)).

Accounting Method

Declare an amortised cost for each operation — the amount you "charge the customer". When the amortised cost exceeds the actual cost, the surplus goes into a credit account. When the actual cost exceeds the amortised cost, credit pays the shortfall.

Example — Dynamic Array

Charge 3 units per insert (amortised O(1)):

• 1 unit pays for inserting the new item.
• 1 unit is credit for that item — used later to copy it when the array doubles.
• 1 unit is credit to pay for copying one of the existing items when doubling next happens.

When capacity doubles from n to 2n, the n items being copied each have at least 1 credit from their own insert plus 1 credit "owed" from a later insert — so the doubling is fully paid for.

Comparison with Potential Method

The accounting method attaches credit to specific items or operations; the potential method tracks a single global Φ for the whole structure. The two are essentially dual — both give valid amortised costs.

Potential Method

Define Φ : States → ℝ with Φ(empty) = 0 and Φ(S) ≥ 0 for all reachable S. For an operation with true cost c taking S_ante → S_post, set:

Example — Dynamic Array with Φ = 2n − c

(where n = items stored, c = current capacity). Check Φ ≥ 0 everywhere (when array is ≥ half full) and Φ(empty) = 0.

• Normal append: c unchanged, n grows. True cost 1. ΔΦ = 2. Amortised = 1 + 2 = O(1).
• Doubling append (n items, cap n → 2n): True cost n + 1. ΔΦ = 2(n+1) − 2n − (2n − n) = 2 − n. Amortised = (n+1) + (2 − n) = 3 = O(1). ✓

Example — Binary Counter

Let Φ = (number of 1s in the counter). An INCREMENT operation that resets r_i bits from 1 to 0 and sets one bit from 0 to 1 costs r_i + 1 true work. ΔΦ = 1 − r_i. Amortised = (r_i + 1) + (1 − r_i) = 2 ∈ O(1). So n increments cost O(n) total. ✓

Designing Good Potential Functions

Priority Queue Implementations Compared

Used with Dijkstra: binary heap gives O(E lg V); Fibonacci heap gives O(E + V lg V), optimal for sparse graphs.

Asymptotically optimal mergeable priority queues: Brodal heaps (1996) and Strict Fibonacci heaps (2012) achieve O(1) actual worst case for INSERT / DECREASE-KEY / UNION and O(lg N) for EXTRACT-MIN. Non-examinable.

Binomial Heap

A Mergeable Priority Queue ADT: supports CREATE, INSERT, PEEK-MIN, EXTRACT-MIN, DECREASE-KEY, DESTRUCTIVE-UNION, COUNT. (DELETE is DECREASE-KEY to −∞ followed by EXTRACT-MIN.)

Binomial Trees B_k

Defined recursively: B₀ is a single node; B_k is formed by linking two B_k−1 trees, one root becoming the leftmost child of the other. (These are not binary trees.)

A Binomial Heap

Collection of binomial trees with:

• Each tree obeys the min-heap property.
• At most one tree of any given degree k (so the roots correspond exactly to the 1-bits in the binary representation of N — e.g. N = 11 = 1011₂ ⟹ trees B₀, B₁, B₃).

Therefore an N-node binomial heap contains ≤ ⌊lg N⌋ + 1 trees, and the overall minimum is one of the roots.

Node Structure

Six fields per node: key, payload, parent pointer, child pointer (to ONE child), sibling pointer, degree. Duplicate keys are permitted. The root list is held in increasing-degree order, threaded through the sibling pointers of the roots.

Operations

BH-CREATE — O(1)

Return NIL (an empty heap).

BH-PEEK-MIN — O(lg N)

Scan the root list (≤ ⌊lg N⌋ + 1 trees) to find the minimum root.

BH-MERGE(bt₁, bt₂) — O(1)

Merge two trees of the same degree: make bt₂ the first child of bt₁ (smaller-key root on top). Increments bt₁.degree; preserves child-list ordering.

BH-DESTRUCTIVE-UNION(bh₁, bh₂) — O(lg N)

Merge the two degree-sorted root lists in one pass (like adding two binary numbers). When two trees of the same degree meet, BH-MERGE them; if a carry results, propagate. The final heap has at most one tree of each degree.

BH-INSERT(bh, (k, p)) — O(lg N)

Create a singleton node (degree 0) — a one-element binomial heap — and BH-DESTRUCTIVE-UNION it with bh.

BH-EXTRACT-MIN(bh) — O(lg N)

1. Use BH-PEEK-MIN (or a stored pointer) to find the minimum root.
2. Cut this tree out of the root list.
3. Reverse its child list (so it is sorted by increasing degree).
4. BH-DESTRUCTIVE-UNION this reversed child list with the remaining root list.

BH-DECREASE-KEY(bh, ptr, nk) — O(lg N)

Same as on a binary min-heap: lower the key, then bubble up by swapping with the parent while the heap property is violated. Height is O(lg N).

Insert: aggregate analysis sketch

A single insert can cost Θ(lg N) in the worst case when it causes a cascade of merges across all degrees — analogous to a binary-counter increment rippling through many 1-bits. But two bad inserts can't happen in a row, and N consecutive inserts from empty total Θ(N) work (same reasoning as binary counter increments). So insert is O(1) amortised.

Fibonacci Heap

Implements the same Mergeable Priority Queue ADT as a binomial heap, but with better amortised bounds: CREATE / PEEK-MIN / COUNT in O(1) actual, INSERT / DECREASE-KEY / UNION in O(1) amortised, and EXTRACT-MIN in O(lg N) amortised.

Structure

A collection of heap-ordered trees held in a doubly linked cyclic root list, unordered. Children of each node are also held in a doubly-linked cyclic list. A pointer minroot tracks the overall minimum in O(1).

Each node has 8 fields: key, payload, left/right sibling pointers, parent pointer, child pointer (to ONE child), degree, marked flag. Nodes in the root list are never marked. The heap itself is a 2-tuple (minroot, N).

Design Rationale — "forward planner"

1. INSERT is lazy: add a singleton to the root list; O(1) true cost, ΔΦ = +1.
2. DECREASE-KEY is lazy: if heap order is violated, cut the node out and dump it into the root list. Don't consolidate.
3. EXTRACT-MIN does batch cleanup: delete minroot, promote its children to the root list, then consolidate roots until no two have the same degree. The potential stored by earlier operations pays for the cleanup.

FH-INSERT(fh, (k, p))

def insert(v, k):
    create singleton node (v, k); marked=false; parent=NIL
    splice into root list
    if k < fh.minroot.key: fh.minroot = new node   # O(1) true cost

FH-EXTRACT-MIN(fh)

def extract-min():
    record (minroot.key, minroot.payload)
    promote each child of minroot to the root list (parent=NIL, marked=false)
    remove minroot
    # Consolidation:
    while two roots have the same degree:
        merge them (keep smaller key on top; increase its degree)
    for each remaining root: update fh.minroot to track min
    return recorded entry

Consolidation uses an auxiliary array A of length D(N) + 1 indexed by degree.

FH-DECREASE-KEY — with Loser Marking

A naive "cut-and-dump" on every violation can produce arbitrarily wide, shallow trees, breaking the O(lg N) bound on max degree. The loser rule preserves shape:

def decrease-key(ptr_k, nk):
    if nk > ptr_k.key: error
    ptr_k.key = nk
    if ptr_k.parent == NIL:
        update fh.minroot if necessary;  return
    if ptr_k.key < ptr_k.parent.key:       # heap violated
        while True:
            p = ptr_k.parent
            cut ptr_k out of p's child list; promote ptr_k to root list
            ptr_k.marked = False
            if p == NIL or not p.marked: break
            ptr_k = p                          # cascade
        if p != NIL: p.marked = True            # but not if p is root
    update fh.minroot if necessary

Fibonacci Heap — Amortised Analysis

Φ(empty) = 0 and Φ ≥ 0 always. Let D(N) denote the maximum degree of any node (we will show D(N) ≤ ⌊log_φ N⌋ where φ = (1+√5)/2).

FH-INSERT — amortised O(1)

True cost O(1). ΔΦ = +1 (one new unmarked root). Amortised = O(1). ✓

FH-DESTRUCTIVE-UNION — amortised O(1)

Splice two root lists and compare minroots. True cost O(1). ΔΦ = 0 (credits carry over). Amortised = O(1). ✓

FH-EXTRACT-MIN — amortised O(D(N)) = O(lg N)

FH-DECREASE-KEY — amortised O(1)

Why D(N) = O(lg N) — Fibonacci Shape Lemma

Conclusion. For any node of degree k in an N-node Fibonacci heap: N ≥ size(x) ≥ φ^k. Taking log_φ: k ≤ ⌊log_φ N⌋ ∈ O(lg N). So D(N) = O(lg N), and EXTRACT-MIN is amortised O(lg N). ✓

Dijkstra with a Fibonacci Heap

Dijkstra does |V| INSERTs + |V| EXTRACT-MINs + ≤ |E| DECREASE-KEYs. With a Fibonacci heap: V · O(1) + V · O(lg V) + E · O(1) = O(E + V lg V) amortised. Optimal for sparse graphs.

Disjoint Sets (Union-Find)

ADT over n distinct keys, initialised with each key in its own set. Operations: MAKE-SET(k), UNION(s₁, s₂), IN-SAME-SET(k₁, k₂). Used by Kruskal to track MST fragments.

Implementations

The Optimal Implementation — Forest with PC + UbR

With both optimisations, m operations on n items run in O(m · α(n)) where α is the inverse Ackermann function. α(n) ≤ 4 for all n ≤ 10⁸⁰, so in practice O(m). Proof of the α bound is beyond this course.

Design-Strategy Analogy

Complete Algorithm Summary

Shortest Path Algorithms

Graph Substructure Algorithms

Data Structure Cost Summary