Graph Algorithms

Recap: BFS finds shortest paths when every edge costs the same

In M26 you met graphs as adjacency lists and explored them with breadth-first search. BFS visits vertices in rings of increasing distance from the source, like ripples from a stone dropped in a pond. In an unweighted graph, the first time BFS reaches a vertex is along a path with the fewest edges, so BFS computes shortest paths in O(V + E).

Real roads have different lengths, though. If edge A–B is a 2-minute walk and A–C–B is two 1-minute walks, the path with fewer edges is not the fastest. A weighted graph attaches a number (the weight or cost) to each edge, and the length of a path is the sum of its weights. We store weighted adjacency lists as {u: [(v, w), ...]}.

Remember: BFS = shortest paths by edge count. For weights, we need a priority queue instead of a plain queue.

Dijkstra's algorithm

Intuition: pour water into the source of a network of pipes whose lengths are the edge weights. The water front spreads at a constant speed and reaches each junction at exactly its shortest distance. Dijkstra's algorithm simulates that front: it repeatedly settles the unsettled vertex closest to the source, then relaxes its outgoing edges.

Relaxing edge (u, v, w) means asking "is going through u a shortcut to v?" If dist[u] + w < dist[v], update dist[v] and record prev[v] = u.

dist[s] = 0; all other dist = infinity
heap = [(0, s)]
while heap:
    d, u = pop the smallest
    if d > dist[u]: continue          # stale entry: lazy deletion
    for (v, w) in neighbors(u):
        if d + w < dist[v]:
            dist[v] = d + w; prev[v] = u
            push (dist[v], v)

Python implementation with heapq and lazy deletion

heapq has no "decrease key" operation. Instead of updating an entry in the heap, we push a new, better entry and leave the old one in place. When the old one is eventually popped, its distance is larger than the recorded best, so we skip it. This is lazy deletion; the heap holds at most E entries, which keeps the complexity at O((V + E) log V).

Why it is correct (proof sketch)

Suppose u is the next vertex popped, with distance d. Any other path from s to u must leave the settled set at some first unsettled vertex x. By the invariant, reaching x already costs at least dist[x] >= d (u was the minimum), and the rest of the path from x to u adds weights that are non-negative, so the path costs at least d. Hence d is optimal, and the invariant survives.

Why negative weights break it

The proof's last step, "the rest of the path cannot make it cheaper," fails if weights can be negative.

B is settled at distance 2 before C is processed, so the cheaper route A→C→B (cost 1) is never used, and D gets 3 instead of 2.

Complexity: O((V + E) log V) time with a binary heap, O(V + E) space. Best case: the target is popped early (you can stop as soon as it is settled). When to use: single-source shortest paths with non-negative weights: road maps, network latency, game movement costs.

Bellman-Ford and negative cycles

Intuition: gossip spreading through a town, one round at a time. In round 1, everyone learns the best route that uses one edge; in round 2, routes with up to two edges; and so on. A shortest path without cycles has at most V − 1 edges, so V − 1 rounds of relaxing every edge are enough.

dist[s] = 0; others = infinity
repeat V - 1 times:
    for each edge (u, v, w):
        if dist[u] + w < dist[v]: dist[v] = dist[u] + w
for each edge (u, v, w):                 # one extra round
    if dist[u] + w < dist[v]: negative cycle reachable!

A negative cycle is a cycle whose weights sum below zero. Going around it again and again makes a path arbitrarily cheap, so "shortest path" is undefined. If anything still improves in round V, a negative cycle must be reachable.

Invariant: after round k, dist[v] is at most the length of the shortest path to v using at most k edges. Complexity: O(V · E) time, O(V) space; best case O(E) with the early exit. When to use: graphs with negative weights (currency exchange with log-rates, where a negative cycle is an arbitrage opportunity; financial adjustments; some network routing protocols, which use the distributed version, distance-vector routing).

Remember: Dijkstra is faster but needs non-negative weights; Bellman-Ford is slower, handles negative weights, and detects negative cycles.

A* search: Dijkstra with a sense of direction

Intuition: Dijkstra explores in all directions equally, like the water front. If you are walking to a landmark you can see, you naturally prefer streets that head toward it. A* (pronounced "A star") orders the frontier by f(n) = g(n) + h(n), where g is the known cost from the start and h is a heuristic estimate of the remaining cost to the goal.

• Admissible: h never overestimates the true remaining cost. A* with an admissible heuristic returns an optimal path.
• Consistent (monotone): for every edge (u, v) with weight w, h(u) <= w + h(v), and h(goal) = 0. Consistent implies admissible, and it guarantees each vertex is settled at most once, just like Dijkstra.
• h = 0 turns A* into Dijkstra. A perfect h walks straight to the goal. An inadmissible h may be faster but can return suboptimal paths (sometimes acceptable in games).

On a grid where you move in 4 directions with cost 1, the Manhattan distance |dr| + |dc| is consistent. With diagonal moves, use the Chebyshev or octile distance; straight-line (Euclidean) distance is admissible for any movement but explores more.

Draw walls in the grid below, then run BFS, Dijkstra, and A* from the same start to the same goal. Count the explored cells: A* explores a narrow band toward the goal, while BFS and Dijkstra flood outward.

Complexity: worst case the same as Dijkstra, O((V + E) log V), but with a good heuristic it explores a small fraction of the graph. Space is its weak point: it stores the whole frontier. When to use: point-to-point search when you know where the goal is and can estimate the distance: maps, game AI, puzzle solving (the 15-puzzle with Manhattan-distance heuristics).

Floyd-Warshall: all pairs at once

Sometimes you need the distance between every pair of vertices: a distance table printed in a road atlas. Floyd-Warshall is a three-line dynamic program. Idea: let d[i][j] be the shortest path from i to j using only vertices 0..k-1 as intermediate stops. Allowing vertex k as well either helps (go i → k → j) or does not.

Invariant: after iteration k, d[i][j] is the shortest i→j path whose intermediate vertices are all in {0, ..., k}. Complexity: Θ(V³) time, Θ(V²) space; handles negative edges and detects negative cycles (a negative diagonal). Use it for small dense graphs (a few hundred vertices); for large sparse graphs, run Dijkstra from each vertex instead. You will meet this style of table-filling again in M32.

Minimum spanning trees: Prim and Kruskal

Problem: a town wants to connect every house to the power grid by laying cable along possible routes, each with a cost. The cheapest network that connects everyone has no cycles (a cycle means one cable is redundant), so it is a tree spanning all vertices: a minimum spanning tree (MST). It applies to connected, undirected, weighted graphs.

The cut property

A cut splits the vertices into two groups. An edge crosses the cut if its endpoints are in different groups. Cut property: for any cut, a lightest crossing edge belongs to some MST (to every MST if weights are distinct). Why: take an MST without that edge e; adding e creates a cycle, which must cross the cut a second time through some edge e′ at least as heavy. Swapping e′ for e gives a spanning tree that is no heavier. Both algorithms below are just different ways of choosing cuts.

Complexity: Prim with a binary heap O(E log V); Kruskal O(E log E) for the sort plus nearly O(E) for union-find. Both use O(V + E) space. Prim suits dense graphs given as adjacency lists; Kruskal suits sparse graphs given as edge lists. When to use: network design (cables, pipes, roads), clustering (stop Kruskal early and the components are clusters), and approximations for the traveling salesman problem.

Cycle detection in directed graphs

In an undirected graph, meeting an already-visited vertex (other than your parent) means a cycle. In a directed graph that is not enough: in A→B, A→C, B→C, vertex C is reached twice but there is no cycle. We need to know whether a vertex is on the current path. Depth-first search with three colors does exactly that:

• White: not yet visited.
• Gray: visiting; on the current DFS path (entered but not finished).
• Black: finished; everything reachable from it has been explored.

An edge to a gray vertex is a back edge: it points to an ancestor on the current path, which closes a cycle. Edges to black vertices are harmless. This is how build systems and package managers (Pixi's solver included) report "circular dependency" errors, and why topological sort fails on cyclic graphs.

The explicit stack of iterators (from M28) avoids the recursion limit. Complexity: O(V + E) time, O(V) space.

Strongly connected components (overview)

In a directed graph, two vertices are strongly connected if each can reach the other. The graph splits into strongly connected components (SCCs): maximal groups where everyone can reach everyone. Collapsing each SCC to a single vertex always leaves a DAG (the condensation), which is why SCCs are the first step in analyzing web link structure, call graphs, and deadlocks.

• Kosaraju's algorithm: DFS the graph and record vertices in order of finishing; then DFS the reversed graph in reverse finishing order. Each tree of the second pass is one SCC. Two passes, O(V + E).
• Tarjan's algorithm: one DFS that tracks each vertex's discovery index and the lowest index reachable (its low-link). When a vertex's low-link equals its own index, it is the root of an SCC. Also O(V + E).

Path reconstruction and real uses

Shortest-path algorithms compute distances; users want routes. Every algorithm in this module can record a predecessor (prev[v] = the vertex before v on the best known path) whenever it improves a distance. Following prev backward from the target to the source and reversing gives the path in O(path length). For Floyd-Warshall, store next[i][j] instead.

Where these algorithms run in the real world

Practice

import heapq
import math

def shortest_path(graph, source, target):
    dist = {source: 0}
    prev = {source: None}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, math.inf):
            continue
        if u == target:
            break
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, math.inf):
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))
    if target not in dist:
        return (math.inf, [])
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = prev[node]
    return (dist[target], path[::-1])

import math

def bellman_ford(n, edges, source):
    dist = [math.inf] * n
    dist[source] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != math.inf and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    for u, v, w in edges:
        if dist[u] != math.inf and dist[u] + w < dist[v]:
            return None
    return dist

import heapq

def astar(grid, start, goal):
    rows, cols = len(grid), len(grid[0])

    def h(cell):
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])

    best = {start: 0}
    heap = [(h(start), 0, start)]
    while heap:
        _, g, cell = heapq.heappop(heap)
        if cell == goal:
            return g
        if g > best[cell]:
            continue
        r, c = cell
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
                ng = g + 1
                if ng < best.get((nr, nc), float("inf")):
                    best[(nr, nc)] = ng
                    heapq.heappush(heap, (ng + h((nr, nc)), ng, (nr, nc)))
    return -1

def kruskal(n, edges):
    parent = list(range(n))

    def find(x):
        root = x
        while parent[root] != root:
            root = parent[root]
        while parent[x] != root:
            parent[x], x = root, parent[x]
        return root

    total = 0
    tree = []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return total, tree

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = dict.fromkeys(graph, WHITE)
    for root in graph:
        if color[root] != WHITE:
            continue
        color[root] = GRAY
        stack = [(root, iter(graph[root]))]
        while stack:
            u, successors = stack[-1]
            advanced = False
            for v in successors:
                if color[v] == GRAY:
                    return True
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append((v, iter(graph[v])))
                    advanced = True
                    break
            if not advanced:
                color[u] = BLACK
                stack.pop()
    return False

Mini-project: metro route planner

pixi init metro && cd metro
pixi add pytest
pixi run python metro.py network.json "Harbor" "University"

{
  "transfer_minutes": 4,
  "lines": {
    "Red":  [["Harbor", 3], ["Central", 2], ["Museum", 4], ["University", 0]],
    "Blue": [["Airport", 6], ["Central", 3], ["Stadium", 5], ["University", 0]]
  }
}

Harbor -> University: 9 min, 0 transfers
  Red: Harbor -> Central -> Museum -> University

Quiz

Recap

• BFS solves unweighted shortest paths; weighted graphs need a priority queue.
• Dijkstra settles vertices in order of distance; lazy deletion makes heapq work; it requires non-negative weights.
• Bellman-Ford relaxes all edges V − 1 times, handles negative weights, and detects negative cycles in O(V · E).
• A* adds an admissible heuristic to focus the search; consistent heuristics settle each vertex once.
• Floyd-Warshall computes all pairs in Θ(V³) with the intermediate-vertex loop outermost.
• Prim and Kruskal build MSTs, both justified by the cut property.
• Three-color DFS finds directed cycles; Kosaraju and Tarjan find SCCs in O(V + E).
• Record predecessors to reconstruct paths; use networkx or scipy for production work.

Going further

• heapq and graphlib.TopologicalSorter (which raises CycleError) in the Python docs
• scipy.sparse.csgraph and networkx algorithms
• Amit Patel, Introduction to A* (Red Blob Games)
• Next: M32 Dynamic Programming builds on the table-filling idea behind Floyd-Warshall.