Shortest Paths & Topological Sort

Basic BFS and DFS answer “what can I reach?” Advanced graph interviews usually ask one of two sharper questions: what order respects these dependencies? or what is the cheapest way to get there? Those are different tools, not just different traversals.

Topological sort works on directed acyclic graphs, where each edge says “this must come before that.” Dijkstra works on weighted graphs with non-negative edge costs, where each relaxation asks whether a newly discovered route is cheaper than the best one you already know.

Both patterns are bookkeeping problems. Topological sort tracks how many prerequisites remain. Dijkstra tracks the best known distance and always expands the currently cheapest unfinished node.

The mental model

A topological order is an ordering of nodes where every directed edge points forward. If a -> b, then a must appear before b. That only makes sense in a DAG; a cycle means there is no valid dependency order.

Kahn’s algorithm treats the graph like a queue of tasks that are ready now:

from collections import deque

def topo_order(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1

    q = deque(i for i in range(n) if indegree[i] == 0)
    order = []

    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)

    return order if len(order) == n else []

The DFS version uses colors: unseen, visiting, done. Reaching a visiting node means you found a back edge, which is a cycle. If there is no cycle, appending a node after its descendants finish gives a postorder that reverses into a valid topological order.

For weighted shortest paths, Dijkstra keeps a min-heap of candidate routes:

import heapq

def dijkstra(graph, source):
    dist = {source: 0}
    heap = [(0, source)]

    while heap:
        cost, node = heapq.heappop(heap)
        if cost != dist[node]:
            continue

        for nxt, weight in graph.get(node, []):
            new_cost = cost + weight
            if new_cost < dist.get(nxt, float("inf")):
                dist[nxt] = new_cost
                heapq.heappush(heap, (new_cost, nxt))

    return dist

Use BFS instead when every edge has the same cost: the first time BFS reaches a node is already the shortest path in number of edges. If edges can be negative, Dijkstra’s “cheapest node is final” assumption breaks; reach for Bellman-Ford or another negative-edge algorithm instead.

Pattern recognition

Variations

Worked problems

Try each yourself before revealing the solution. The first two are the same dependency graph viewed two ways; the third switches to weighted shortest paths.

from collections import deque

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    q = deque(i for i in range(num_courses) if indegree[i] == 0)
    taken = 0

    while q:
        course = q.popleft()
        taken += 1

        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)

    return taken == num_courses

def find_order(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    color = [0] * num_courses
    order = []

    def dfs(course):
        if color[course] == 1:
            return False
        if color[course] == 2:
            return True

        color[course] = 1
        for nxt in graph[course]:
            if not dfs(nxt):
                return False

        color[course] = 2
        order.append(course)
        return True

    for course in range(num_courses):
        if color[course] == 0 and not dfs(course):
            return []

    return order[::-1]

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    dist = [float("inf")] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]

    while heap:
        time, node = heapq.heappop(heap)
        if time != dist[node]:
            continue

        for nxt, weight in graph[node]:
            new_time = time + weight
            if new_time < dist[nxt]:
                dist[nxt] = new_time
                heapq.heappush(heap, (new_time, nxt))

    answer = max(dist[1:])
    return -1 if answer == float("inf") else answer

The classic pitfall

When the graph has unit weights, choose BFS. When it has non-negative weights, choose Dijkstra. When the graph is about prerequisites, choose topological sort. Most mistakes come from reaching for the right family one step too late.