Graph Algorithms

Building on the graphs page#

The data structures course's graphs page covered graph terminology, the adjacency list/matrix representations, and traversal with BFS and DFS — including using BFS to find the shortest path in an unweighted graph (fewest hops). This page tackles two more specialized problems that come up constantly in practice: finding the cheapest path through a graph whose edges have different costs, and efficiently tracking which nodes belong to the same connected group as a graph grows over time.

Dijkstra's algorithm: shortest path in a weighted graph#

BFS finds the shortest path by hop count, but it has no way to account for edges that cost different amounts — a path with fewer hops can still be more expensive in total weight than a path with more (but cheaper) hops. Dijkstra's algorithm finds the true shortest weighted path from a starting node to every other node, correctly accounting for varying edge weights — as long as those weights are never negative (more on why below).

Analogy: planning a road trip by always driving next to whichever reachable-but-not-yet-finalized city currently has the cheapest known total cost to reach — because taking a detour through a more expensive city first can only ever make future costs worse, never better. This is exactly BFS's "explore in order of distance" idea, upgraded to handle unequal edge costs by swapping the plain queue for a priority queue, so the algorithm always expands whichever node currently has the cheapest known distance next, rather than simply whichever node was enqueued next.

import heapq

def dijkstra(graph, start):
    # graph: adjacency list shaped like {node: [(neighbor, weight), ...]}
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]        # (distance_so_far, node)

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)

        if current_dist > distances[current_node]:
            continue                      # a shorter path was already found — skip this stale entry

        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:      # found a cheaper path to neighbor
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("A", 4), ("D", 1)],
    "C": [("A", 1), ("B", 2), ("D", 5)],
    "D": [("B", 1), ("C", 5)],
}

print(dijkstra(graph, "A"))   # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

Tracing it from "A": start with distances = {A:0, B:inf, C:inf, D:inf} and the queue holding (0, A). Pop (0, A): relax its neighbors — B becomes 4, C becomes 1; push both. Pop (1, C) (cheapest remaining): relax C's neighbors — A via C would be 2, worse than 0, skip; B via C would be 1 + 2 = 3, better than 4, update B to 3; D via C would be 1 + 5 = 6, better than inf, update D to 6. Pop (3, B) (now the cheapest): relax B's neighbors — A via B would be worse, skip; D via B would be 3 + 1 = 4, better than 6, update D to 4. The queue still holds a stale (4, B) and (6, D) from earlier, less-optimal pushes — popping them next finds current_dist > distances[node] and skips them harmlessly. Final distances: {A: 0, B: 3, C: 1, D: 4}.

This runs in O((V + E) log V) using a binary heap — each edge can trigger at most one push (O(log V) each), and each node is finalized or skipped in O(log V) pop time. That's a meaningful improvement over a naive O(V²) approach that scans every remaining node for the current minimum at each step, especially on sparse graphs (the common case, per the graphs page).

Why non-negative weights are required: Dijkstra's entire approach rests on the assumption that once a node is popped from the priority queue with the smallest known distance, that distance is final and can never improve later. That assumption only holds because every additional edge can only ever increase total distance when weights are non-negative — adding more edges never helps. If a negative edge weight existed, a longer path discovered later could sneak in a negative-weight edge and undercut a distance that was already treated as "finalized," silently breaking that core assumption and producing a wrong answer with no error raised.

When you need Bellman-Ford instead: negative weights#

Bellman-Ford correctly handles graphs with negative edge weights (and can additionally detect negative-weight cycles — cycles you could loop around forever to make the total cost arbitrarily low, which makes "shortest path" ill-defined in the first place). It works by relaxing every edge, repeatedly, V - 1 times, rather than greedily trusting whichever distance currently looks smallest — that repeated, non-greedy relaxation is exactly what lets it tolerate negative edges correctly. The cost is speed: Bellman-Ford runs in O(V × E), meaningfully slower than Dijkstra's O((V + E) log V).

Rule of thumb: reach for Dijkstra by default — it's faster and perfectly correct for the overwhelming majority of real-world weighted graphs (road distances, flight costs, network latency all naturally have non-negative weights). Reach for Bellman-Ford specifically when negative edge weights are genuinely possible in your problem — for instance, modeling costs that can represent rebates or gains as well as expenses.

Union-Find (Disjoint Set Union) for connectivity#

Union-Find (also called Disjoint Set Union, or DSU) answers two questions efficiently as a graph's connections are built up incrementally: "are these two nodes in the same connected group?" and "merge these two groups into one" — without needing to re-run a full BFS or DFS traversal from scratch every single time something changes.

Analogy: think of friend groups at a party. Each group has one designated representative who speaks for the whole group. Checking whether two people belong to the same group just means comparing who their groups' representatives are. When two groups merge (someone introduces two friend circles to each other), one group's representative simply starts reporting to the other's.

Two core operations: find(x) — which group does x belong to (returns that group's representative, or "root")? union(x, y) — merge x's group and y's group into one. A naive implementation can degrade to O(n) per find in the worst case (a long chain of nodes each pointing to the next). Two standard optimizations fix that: path compression (during find, make every visited node point directly to the root, flattening future lookups) and union by rank (when merging, always attach the shorter tree under the taller tree's root, keeping trees shallow). Together, they bring the amortized cost of either operation down to nearly O(1) — formally O(α(n)), where α is the inverse Ackermann function, which grows so slowly that it's effectively a small constant (≤ 4) for any input size you'd realistically encounter.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))     # each node starts as its own group's representative
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # path compression: flatten the chain
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False                   # already in the same group

        # union by rank: attach the shorter tree under the taller tree's root
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True


uf = UnionFind(6)          # nodes 0..5, each its own group initially
uf.union(0, 1)
uf.union(1, 2)
uf.union(3, 4)

print(uf.find(0) == uf.find(2))   # True  -> 0 and 2 were merged together via 1
print(uf.find(0) == uf.find(3))   # False -> still different groups

Tracing the unions: union(0, 1) — both are their own roots with rank 0; 1's root attaches under 0's, and since ranks tied, 0's rank bumps to 1. union(1, 2) — find(1) returns 0 (its root), find(2) returns 2; 2 attaches under 0 (rank 1 beats rank 0, no rank change). union(3, 4) — both roots, tied ranks; 4 attaches under 3, and 3's rank bumps to 1. After these three unions: find(0) and find(2) both resolve to 0 (True), while find(3) resolves to 3, a completely separate group from 0 (False) — matching the printed output exactly.

Real use case: detecting whether adding an edge would create a cycle while building up a graph incrementally, counting connected components, "friend circle" style problems, and grouping connected regions in image processing — anywhere a graph's connectivity needs to be queried repeatedly as edges are added, rather than computed once for a fixed, finished graph.

Common mistakes#

• Skipping path compression or union by rank, letting the Union-Find structure degrade into a long chain — effectively a linked list, with O(n) find operations instead of near-O(1).
• Running Dijkstra on a graph that might contain negative edge weights. It won't crash — it will silently produce an incorrect shortest path, since its core "once finalized, always final" assumption quietly breaks.
• Re-running a full BFS/DFS every time a connectivity question needs answering, when the graph is being built up incrementally — Union-Find answers the same question far more cheaply by maintaining the structure as you go, instead of recomputing it from scratch.
• Forgetting the stale-entry check (if current_dist > distances[current_node]: continue) in a heap-based Dijkstra implementation — without it, outdated queue entries get processed unnecessarily, wasting time (though, importantly, without producing an incorrect final answer).