Shortest Path (BFS)

Reconstructing the Shortest Path

Dijkstra finds shortest distances, but often you need the actual path — the sequence of nodes to traverse.

For unweighted graphs, BFS naturally finds the shortest path. For weighted graphs, modify Dijkstra to track predecessors.

BFS with Parent Tracking

from collections import deque

def shortest_path(graph, src, dst):
    if src == dst:
        return [src]
    parent = {src: None}
    queue = deque([src])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in parent:
                parent[nb] = node
                if nb == dst:
                    # Reconstruct: follow parent pointers back
                    path = []
                    curr = dst
                    while curr is not None:
                        path.append(curr)
                        curr = parent[curr]
                    return path[::-1]
                queue.append(nb)
    return []    # no path found

Reconstruction Pattern

The trick is to store where we came from (parent dict). When we reach the destination, we walk backward through the parents and reverse the result:

path = []
curr = dst
while curr is not None:
    path.append(curr)
    curr = parent[curr]
return path[::-1]

Your Task

Implement shortest_path(graph, src, dst) that returns the list of nodes on the shortest path (BFS) from src to dst. Return an empty list if no path exists.