Shortest Paths & Topological Sort

Graphs, lesson 2 of 3

Shortest Paths & Topological Sort

BFS for fewest steps, multi-source BFS, and ordering dependencies with Kahn's algorithm.

14 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

BFS finds shortest paths when every edge costs the same. It explores in rings of distance 0, 1, 2, ..., so the first time it reaches a node, it reached it by the fewest possible steps.

Signals: "minimum number of moves / steps / transformations", "nearest", "how many minutes until ...", on an unweighted graph or grid.

Two ways to track the distance:

  • process the queue one layer at a time (for _ in range(len(queue))) and bump a steps counter after each layer, or
  • store dist[node] and set dist[nxt] = dist[node] + 1 on enqueue.
Example

Fewest steps through a maze (layer by layer)

Each printed line is one "ring". The goal first shows up in ring 5, so 5 moves is the minimum. Put a # at (2, 2) and (1, 3) and the answer becomes -1.

Quiz

What does this print?

Multi-source BFS. "Distance to the nearest shop / exit / rotten orange" has many starting points. Instead of one BFS per source (slow), put all sources in the queue at distance 0 and run a single BFS. The rings now spread from every source at once, and each cell is claimed by whichever source reaches it first, which is the nearest one. Total cost: one O(rows × cols) pass.

Example

Distance to the nearest shop

dist doubles as the visited marker (-1 = unvisited). The largest value in dist is "how long until everything is reached": exactly the question in Rotting Oranges.

Topological sort. Dependencies ("take course B before A", "build lib before app") form a directed graph. A topological order lists every node so each edge before → after points forward. It exists only if there is no cycle (a DAG).

Kahn's algorithm peels off nodes with nothing left to wait for:

  1. Count each node's in-degree (incoming edges).
  2. Queue every node with in-degree 0.
  3. Pop a node, append it to the order, and decrement each neighbour's in-degree; any that hit 0 join the queue.
  4. If the order has fewer than n nodes, the rest are stuck in a cycle.

Cost: O(V + E).

Example

Kahn's algorithm, traced

In the second call, 1 and 2 wait on each other forever: only node 0 is ever taken, so the function reports the cycle with []. Several orders can be valid; Kahn's returns one of them.

Quiz

What does this print?

Exercise

Fewest hops

Write fewest_hops(n, edges, src, dst) for an undirected graph with nodes 0..n-1. Return the smallest number of edges on a path from src to dst, 0 if they are the same node, or -1 if dst can't be reached.

fewest_hops(5, [(0, 1), (1, 2), (0, 3), (3, 2), (2, 4)], 0, 4) is 3.

Quiz

Why is BFS, not DFS, the tool for "fewest moves" on an unweighted grid?