Graphs: Topo Sort & Dijkstra

Dependency ordering, cycle detection and weighted shortest paths.

Beyond basic BFS and DFS, two graph algorithms come up again and again: topological sort for ordering dependencies, and Dijkstra for shortest paths with weights.

Representing a graph

Most problems give you an edge list. Convert it to an adjacency list:

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)        # directed; add graph[v].append(u) for undirected

Topological sort

Orders the nodes of a directed acyclic graph so every edge goes from earlier to later. Use it for course prerequisites, build systems, task scheduling — anything with "X must happen before Y".

Signals: dependencies, prerequisites, "valid order", "can all tasks be completed?"

from collections import deque, defaultdict

def topo_sort(n, edges):
    graph = defaultdict(list)
    indegree = [0] * n
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1

    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    return order if len(order) == n else []   # shorter = there's a cycle

O(V + E). The "fewer than n nodes processed" check doubles as cycle detection.

Dijkstra's algorithm

Shortest paths from one source when edge weights are non-negative.

import heapq
from collections import defaultdict

def dijkstra(n, edges, source):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))

    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue                      # stale entry
        for nxt, w in graph[node]:
            nd = d + w
            if nd < dist[nxt]:
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))
    return dist

O((V + E) log V).

Choosing a shortest-path algorithm

[!TIP] Practice Course Schedule · Network Delay Time