Algorithms Practice Lesson 4 of 4

BFS shortest path

Breadth-first search (BFS) explores a graph in rings: first the start node, then everything one step away, then everything two steps away, and so on. Because it reaches every node in order of distance, the very first time it touches the target it has found a shortest path there - no route with fewer hops could have been missed.

The classic way to do this is a queue of paths. Start with the path [start]. Pull a path off the front, look at its last node, and for each neighbor build a new path with that neighbor tacked on. If a neighbor is the target, that extended path is your answer. Mark nodes as visited when you enqueue them so you never loop back on yourself or waste time on a longer route to a node you have already reached.

Your task: write bfs_shortest_path(graph, start, target), where graph is a dict mapping each node to a list of its neighbors. Return the shortest path from start to target as a list of nodes (including both ends), or None if the target cannot be reached. If start equals target, the path is just [start].

You'll practice:

Exploring a graph level by level with a queue
Tracking visited nodes and reconstructing the path you took

# Return the shortest path from start to target as a list of nodes, or None.
# graph is a dict mapping each node to a list of its neighbor nodes.
def bfs_shortest_path(graph, start, target):
    pass