Shortest Path in an Unweighted Graph

Difficulty: Medium · Pattern: Graph BFS · Concept: General Coding (DSA) — Core Patterns to Drill

Given a graph as an adjacency list and a start and end node, find the length of the shortest path between them — measured in number of edges, since the graph is unweighted (every edge costs the same).

DFS explores one path as deep as it can go before backing up — it can find a path, but not necessarily the shortest one. BFS explores level by level, radiating outward from the start node one edge at a time — the first time it reaches the end node is guaranteed to be via the shortest path, because every node at distance $d$ is visited before any node at distance $d+1$ .

Your task: implement shortest_path_length(graph, start, end), where graph is a dict mapping each node to a list of its neighbors. Return -1 if end is unreachable from start.

Implement it yourself

assert shortest_path_length({"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"]}, "A", "E") == 3
assert shortest_path_length({"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"]}, "A", "A") == 0
assert shortest_path_length({"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"]}, "A", "D") == 2
assert shortest_path_length({"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"]}, "E", "A") == 3
assert shortest_path_length({"X": ["Y"], "Y": ["X"], "Z": []}, "X", "Z") == -1

Next: Rotting Oranges (Multi-Source BFS) (a harder BFS variant), or continue to Count Islands (Connected Components)