Week 15: Advanced Graphs — Minimum Spanning Trees & Shortest Paths II

1. Minimum Spanning Trees: Kruskal's Algorithm

A spanning tree of a connected, undirected, weighted graph is a subset of its edges that connects every node with no cycles — exactly n - 1 edges for n nodes. A minimum spanning tree (MST) is the spanning tree whose edge weights sum to the least possible total, the graph-theory version of "cheapest way to wire every node together." Kruskal's algorithm builds one greedily: sort every edge by weight, then repeatedly add the cheapest remaining edge unless it would connect two nodes already in the same component — which is exactly the question Week 12's Union-Find answers in near-O(1).

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

struct Edge { int u, v, weight; };

struct DSU {
    vector<int> parent, rank_;
    DSU(int n) : parent(n), rank_(n, 0) { iota(parent.begin(), parent.end(), 0); }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;               // already connected -- would form a cycle
        if (rank_[ra] < rank_[rb]) swap(ra, rb);
        parent[rb] = ra;
        if (rank_[ra] == rank_[rb]) rank_[ra]++;
        return true;
    }
};

// Returns the MST's total weight -- O(E log E) time, dominated by the sort
int kruskalMST(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(),
         [](const Edge& a, const Edge& b) { return a.weight < b.weight; });

    DSU dsu(n);
    int totalWeight = 0, edgesUsed = 0;

    for (const Edge& e : edges) {
        if (dsu.unite(e.u, e.v)) {          // only adds the edge if it doesn't form a cycle
            totalWeight += e.weight;
            edgesUsed++;
            if (edgesUsed == n - 1) break;  // spanning tree is complete
        }
    }
    return totalWeight;
}

Sorting the edges costs O(E log E), and each of the E Union-Find operations is nearly O(1) with path compression and union by rank — so the sort dominates, giving O(E log E) overall. Kruskal's greedy choice is provably safe: the cheapest edge in the whole graph can always be added to some MST without ever needing to be removed later, which is what lets a purely local decision (is this the cheapest remaining edge that doesn't cycle?) build a globally optimal structure.

2. Minimum Spanning Trees: Prim's Algorithm

Prim's algorithm builds the same minimum spanning tree by growing a single tree one node at a time, instead of considering all edges globally: start from any node, and repeatedly add the cheapest edge that connects the growing tree to a node not yet in it. That "cheapest edge available right now" question is exactly what a min-heap priority queue answers in O(log n), the same structure Week 11 used for the top-K pattern.

#include <vector>
#include <queue>
#include <climits>
using namespace std;

// adj[u] = list of {weight, v} for each edge u--v -- O(E log V) time
int primMST(int n, vector<vector<pair<int,int>>>& adj) {
    vector<bool> inMST(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;  // {weight, node}
    pq.push({0, 0});   // start from node 0 with a free "entry edge"

    int totalWeight = 0, nodesAdded = 0;

    while (!pq.empty() && nodesAdded < n) {
        auto [weight, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;             // stale entry -- a cheaper edge to u already won

        inMST[u] = true;
        totalWeight += weight;
        nodesAdded++;

        for (auto& [w, v] : adj[u]) {
            if (!inMST[v]) pq.push({w, v});  // candidate edge into the growing tree
        }
    }
    return totalWeight;
}

Every node can be pushed onto the heap once per incident edge, so the heap holds up to O(E) entries, and each push/pop costs O(log E) — giving O(E log E) overall, the same bound as Kruskal's, though Prim's tends to win on dense graphs where E is close to V². The if (inMST[u]) continue; line is essential: because the same node can be pushed multiple times at different candidate weights before its cheapest edge is popped, skipping already-settled nodes is what keeps a stale, more expensive entry from corrupting the running total — the same "lazy deletion" idea Dijkstra's implementation in Week 12 relies on.

3. Bellman-Ford: Shortest Paths with Negative Weights

Dijkstra's algorithm assumes every edge weight is non-negative — its greedy "the closest unvisited node's distance is already final" claim breaks the moment a negative edge exists, because a longer-looking path could later use a negative edge to become cheaper. Bellman-Ford drops that assumption. Instead of greedily finalizing one node at a time, it relaxes every edge, V - 1 times over:

#include <vector>
#include <climits>
using namespace std;

struct Edge { int u, v, weight; };

// Returns distances from src, or an empty vector if a negative cycle is reachable
// O(V * E) time
vector<long long> bellmanFord(int n, vector<Edge>& edges, int src) {
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;

    for (int i = 0; i < n - 1; i++) {                 // relax every edge V-1 times
        for (const Edge& e : edges) {
            if (dist[e.u] == LLONG_MAX) continue;      // u not reachable yet
            if (dist[e.u] + e.weight < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.weight;
            }
        }
    }

    // One more pass: if anything still relaxes, a negative-weight cycle is reachable from src
    for (const Edge& e : edges) {
        if (dist[e.u] != LLONG_MAX && dist[e.u] + e.weight < dist[e.v]) {
            return {};    // signal: negative cycle detected, shortest paths are undefined
        }
    }
    return dist;
}

Any shortest path visits at most V - 1 edges (a path that revisits a node could only be shortened by removing the cycle, assuming no negative cycle exists), so after V - 1 full relaxation passes every shortest distance is guaranteed correct — that bound is exactly where the O(V · E) time complexity comes from, noticeably slower than Dijkstra's O(E log V). The extra V-th pass is what makes Bellman-Ford useful beyond "slower Dijkstra": if any edge can still be relaxed after V - 1 passes should have stabilized everything, that's proof a negative-weight cycle is reachable and pulling the "shortest path" toward negative infinity.

4. Floyd-Warshall: All-Pairs Shortest Paths

Dijkstra's and Bellman-Ford both answer "shortest path from one source." When a problem needs the shortest distance between every pair of nodes, running one of those V times costs at least O(V · E log V). Floyd-Warshall answers the same question directly in O(V³) with dynamic programming: dist[i][j] is repeatedly improved by asking "is going through node k shorter than the current best?", for every k in turn.

#include <vector>
#include <climits>
using namespace std;

const long long INF = LLONG_MAX / 2;   // avoid overflow when adding two INFs

// dist[i][j] initialized to edge weight, or INF if no direct edge, 0 if i == j
// O(V^3) time, O(V^2) space
void floydWarshall(vector<vector<long long>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; k++) {              // try routing through k
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

The loop order is the entire algorithm: by the time k finishes its pass, dist[i][j] is the shortest path using only intermediate nodes from {0, ..., k} — an interval-DP-flavored invariant, expanding the allowed set of intermediate nodes one at a time rather than expanding a range. It handles negative edges correctly (unlike Dijkstra's) as long as no negative cycle exists; a negative value appearing on the diagonal, dist[i][i] < 0, after running is the all-pairs equivalent of Bellman-Ford's extra relaxation check.

5. Hands-on Exercise

6. Knowledge Check

Four quick questions. Expand each to check your answer.