Minimum Spanning Trees, Shortest Paths, A* & PageRank

Given a connected, undirected weighted graph $G = (V, E, w)$, a Minimum Spanning Tree (MST) is a spanning tree $T = (V, E_T)$ with $|E_T| = |V| - 1$ edges that minimises the total edge weight $w(T) = \sum_{e \in E_T} w(e)$.

Algorithm Prim_Array(G, v0):
    For each vertex v in G do:
        cost[v] <- infinity
        prev[v] <- null
    End do
    cost[v0] <- 0
    Q <- list of all vertices in G

    While Q is not empty do:
        u <- vertex in Q with minimum cost[u]
        remove u from Q
        For each neighbour v of u do:
            If v in Q and weight(u, v) < cost[v] then:
                cost[v] <- weight(u, v)
                prev[v] <- u
            End if
        End do
    End do
    Return prev
End Algorithm

Algorithm Prim_PQ(G, v0):
    Q <- new Min-Priority Queue
    For each vertex v in G do:
        cost[v] <- infinity
        prev[v] <- null
        enqueue(Q, v, cost[v])
    End do
    // -infinity ensures v0 is pulled first even with negative edges!
    cost[v0] <- -infinity
    requeue(Q, v0, cost[v0])

    While Q is not empty do:
        u <- peek(Q); dequeue(Q)
        For each (u, v) with weight w in Edges(G, u) do:
            If v in Q and w < cost[v] then:
                cost[v] <- w
                prev[v] <- u
                requeue(Q, v, w)
            End if
        End do
    End do
    Return prev
End Algorithm

Algorithm Kruskal(G):
    T <- Graph with all vertices V and no edges
    L <- list of all edges in E, sorted by weight ascending
    For each edge (u, v) in L do:
        If adding (u, v) to T does not create a cycle then:
            Add edge (u, v) to T
        End If
        If |E(T)| == |V| - 1 then:
            Return T
        End If
    End For
    Return T
End Algorithm

HESS Manual Table Method for Hand-Tracing Prim's Algorithm

In the HESS study guide, Prim's algorithm is hand-traced using a (distance, parent) state table where each column represents a vertex $v \in V$ and each row represents the state of the Priority Queue after adding a vertex to the MST:

1. Create a table with columns for every vertex (in lexicographical/alphabetical order). Initialise all cells to (∞, nil).
2. Row 1 (Initialisation): Set the starting (lexicographically first) vertex $v_0$ to (0, nil) and all other vertices to (∞, nil). Circle (0, nil).
3. Update Neighbours: Add the circled vertex $u$ as the label of the next row. For every unvisited vertex $v$, if the edge weight $w(u, v)$ is smaller than $v$'s current distance in the previous row, update cell $v$ to (w(u, v), u); otherwise, copy its previous (distance, parent) entry down.
4. Select Minimum & Tie-Breaking: In the current row, circle the unvisited cell with the minimum distance, breaking any ties in lexicographical (alphabetical) order. Cross out / lock that column for subsequent rows.
5. Repeat until all $|V|$ vertices have been circled; the circled (distance, parent) pairs directly list the $|V|-1$ MST edges and their weights!

Formal Correctness Proof of Prim's Algorithm (Loop Invariant)

In the HESS notes, Prim's algorithm is proven correct by establishing the Loop Invariant: At the start of each iteration of the while loop, the subtree $T$ is a subgraph of some Minimum Spanning Tree $T^*$ of $G$.

The Single-Source Shortest Path problem asks for the minimum-weight path from a starting source vertex $s$ to every other vertex $v \in V$.

Algorithm Dijkstra(G, source):
    let Q be a Min-Priority Queue
    dist[source] <- 0
    prev[source] <- undefined
    For each vertex v in G do:
        If v != source then:
            dist[v] <- infinity
            prev[v] <- undefined
        End If
        Q.insertWithPriority(v, dist[v])
    End For

    While Q is not empty do:
        u <- Q.pullMin()
        For each neighbour v of u do:
            alt <- dist[u] + weight(u, v)
            If alt < dist[v] then:
                dist[v] <- alt
                prev[v] <- u
                Q.decreasePriority(v, alt)
            End If
        End For
    End While
    Return dist[], prev[]
End Algorithm

Algorithm BellmanFord(G, source):
    For each vertex v in V do:
        dist[v] <- infinity
        prev[v] <- null
    End For
    dist[source] <- 0

    // Relax all edges |V| - 1 times
    For i from 1 to |V| - 1 do:
        For each edge (u, v) with weight w in E do:
            If dist[u] + w < dist[v] then:
                dist[v] <- dist[u] + w
                prev[v] <- u
            End If
        End For
    End For

    // |V|-th pass: check for negative-weight cycles
    For each edge (u, v) with weight w in E do:
        If dist[u] + w < dist[v] then:
            Error "Graph contains a negative-weight cycle"
        End If
    End For
    Return dist[], prev[]
End Algorithm

• Why Dijkstra Fails on Negative Edges: Dijkstra greedily locks in the vertex $u$ with the smallest tentative distance $\text{dist}[u]$, assuming adding future edges can only increase path cost. A negative edge $w(x, u) < 0$ discovered later can reduce the cost to $u$ after $u$ has already been extracted from the Priority Queue.
• Why Bellman-Ford Relaxes $|V| - 1$ Times: Any simple shortest path (without cycles) in a graph of $|V|$ vertices contains at most $|V| - 1$ edges. Relaxing every edge in $E$ across $|V| - 1$ passes ($\Theta(|V| \cdot |E|)$ time) guarantees optimal distances unless a negative-weight cycle is reachable, which is caught if any edge can still be relaxed on the $|V|$-th pass.

Both Warshall's Algorithm (transitive closure / reachability) and Floyd-Warshall's Algorithm (all-pairs shortest paths) use Dynamic Programming over an $n \times n$ matrix ($n = |V|$), incrementally allowing vertices $\{1, 2, \dots, k\}$ as intermediate stepping stones. Both run in $\Theta(|V|^3)$ time and $\Theta(|V|^2)$ space.

In the HESS notes, Warshall's and Floyd-Warshall's qualify as Dynamic Programming for two foundational reasons: (1) they decompose paths into trivial subproblems (direct edges of length 1 when $k = 0$) versus non-trivial subproblems (paths routed through intermediate vertices $\{1 \dots k\}$), and (2) they exhibit overlapping subproblems (every path from $i$ to any $j$ via $k$ reuses the cached sub-path $(i, k)$). Furthermore, Floyd-Warshall is structurally identical to Warshall's algorithm under min-plus algebra (replacing Boolean $\lor$ with $\min$ and Boolean $\land$ with $+$).

Algorithm Warshall_Improved(A[1..n, 1..n]):
    T <- A // k = 0 base case: Boolean adjacency matrix
    For k from 1 to n do:
        For i from 1 to n do:
            // HESS Optimisation: only scan row j if i can reach k!
            If T[i, k] == 1 then:
                For j from 1 to n do:
                    T[i, j] <- T[i, j] OR T[k, j]
                End For
            End If
        End For
    End For
    Return T
End Algorithm

Algorithm FloydWarshall(G):
    let dist be a |V| x |V| matrix initialised to infinity
    For each vertex v in V do:
        dist[v, v] <- 0
    End For
    For each edge (u, v) with weight w in E do:
        dist[u, v] <- w
    End For

    For k from 1 to |V| do:
        For i from 1 to |V| do:
            For j from 1 to |V| do:
                If dist[i, k] + dist[k, j] < dist[i, j] then:
                    dist[i, j] <- dist[i, k] + dist[k, j]
                End If
            End For
        End For
    End For
    Return dist
End Algorithm

A* Search combines the exact cost-so-far of Dijkstra's algorithm with the goal-directed heuristic estimate of Best-First Search. Each node $n$ in the Min-Priority Queue is ordered by the evaluation function:

• $g(n)$: The exact known shortest path weight from the start node to $n$.
• $h(n)$: The heuristic estimated cost from $n$ to the target goal node.
• Admissible Heuristic Requirement: A* is guaranteed to find the optimal (shortest) path if and only if $h(n)$ is admissible—meaning $0 \le h(n) \le h^*(n)$ for all $n$, where $h^*(n)$ is the true minimum cost to reach the goal. An admissible heuristic never overestimates the remaining distance (it is optimistic). Note that when $h(n) = 0$ everywhere, A* degenerates into Dijkstra's Algorithm.

Algorithm A*(Graph, source, goal):
    open <- Min-Priority Queue
    For each vertex v in Graph do:
        v.dist <- infinity
        v.parent <- null
        v.h <- h(v, goal)
    End do
    source.dist <- 0
    source.value <- source.dist + source.h
    enqueue(open, source, source.value)

    While open is not empty do:
        u <- peek(open); dequeue(open)
        If u == goal then:
            Return u.parent // Reconstruct optimal path
        End if
        For each neighbour v of u do:
            If u.dist + weight(u, v) < v.dist then:
                v.dist <- u.dist + weight(u, v)
                v.value <- v.dist + v.h
                v.parent <- u
                If v in open then:
                    requeue(open, v, v.value)
                Else:
                    enqueue(open, v, v.value)
                End if
            End if
        End do
    End do
    Return failure
End Algorithm

PageRank models the web as a directed graph $G = (V, E)$ where vertices are webpages and directed edges $(B, A)$ are hyperlinks from page $B$ to page $A$. A page's importance is defined recursively by the importance of the pages linking to it, divided by their total outbound links $L(B)$:

• $PR(A_i)$: The PageRank of node $A$ at iteration $i$ (initialised at $i = 0$ to $PR(v_0) = \frac{1}{|V|}$ for all nodes).
• $d$: The damping factor (typically $d = 0.85$), representing the probability that a random surfer clicks a link on the current page rather than teleporting to a random page ($1 - d = 0.15$).
• $M(A)$: The set of pages that have an outbound link pointing into $A$.
• $L(B)$: The out-degree $\deg^+(B)$ (total outbound links from page $B$).
• Sink Nodes (Dead Ends, outdegree == 0): If a page $S$ has no outbound links ($L(S) = 0$), it is a sink node that would drain PageRank from the system. In the HESS specification, before running PageRank iterations, every sink node has virtual outbound edges added to every node in the graph, including itself (so $L(S) = |V|$).

Worked Example from HESS Notes: 4-Node Web Graph (Nodes 1, 2, 3, 4 with Sink Node 2)

In the HESS study notes, consider the 4-node directed graph $V = \{1, 2, 3, 4\}$ ($|V| = 4$, damping factor $d = 0.85$, teleportation term $\frac{1 - 0.85}{4} = 0.0375$) with directed edges:

• Node 1 links to Node 2 and Node 3 ($L(1) = 2$).
• Node 2 has zero outbound links ($\text{outdegree} = 0$)—it is a sink node! By the HESS sink-node rule, virtual outbound links are added from Node 2 to all 4 nodes (1, 2, 3, and 4, including Node 2 itself), giving $L(2) = 4$.
• Node 3 links to Node 2 and Node 4 ($L(3) = 2$).
• Node 4 links to Node 3 ($L(4) = 1$).

Algorithm PageRank(G, d, iterations):
    N <- |V(G)|
    // Step 1: Convert sink nodes (outdegree = 0) by linking to all nodes
    For each node n in V(G) do:
        If n.outdegree == 0 then:
            For each node m in V(G) do:
                add directed edge (n, m) to G
            End do
            n.outdegree <- N
        End if
        PR[n] <- 1 / N
    End do

    // Step 2: Iterative power-method update
    For iter from 1 to iterations do:
        For each node u in V(G) do:
            sum <- 0
            For each node v in Inbound(G, u) do:
                sum <- sum + (PR[v] / v.outdegree)
            End do
            newPR[u] <- ((1 - d) / N) + d * sum
        End do
        PR <- newPR
    End do
    Return PR
End Algorithm

• I can prove Prim's Algorithm correct using the Loop Invariant (Initialization, Maintenance via Cut Property exchange argument, Termination).
• I can state and apply the $\Theta(|V|^3)$ DP recurrences for Warshall's ($T_{i,j}^k$) and Floyd-Warshall's ($W_{i,j}^k$) algorithms.
• I can compute PageRank iterations by hand using $PR(A_i) = \frac{1-d}{|V|} + d \sum \frac{PR(B_{i-1})}{L(B)}$ and handle sink nodes properly.