Shortest Path in Unweighted Graphs
You'll learn how BFS naturally finds the shortest path in unweighted graphs by tracking distances and parent relationships.
The Core Idea
When you run BFS from a source vertex, you explore nodes level by level—first all nodes 1 edge away, then 2 edges away, and so on. This guarantees that when you first reach any node, you've found the shortest path to it (measured by number of edges).
To reconstruct the actual path, we need to remember:
- Distance from source to each vertex
- Parent pointers: which vertex led us to each node
- Path reconstruction: follow parent pointers backward
How It Works
Think of BFS as water spreading outward from a source. The first "wave" that touches each spot traveled the shortest route. We just need to leave breadcrumbs (parent pointers) to trace back.
During BFS traversal:
- Initialize distance of source to
0, all others to infinity (or -1) - When discovering a neighbor, set:
distance[neighbor] = distance[current] + 1parent[neighbor] = current
To reconstruct the shortest path from source to target:
- Start at target
- Follow parent pointers backward until reaching source
- Reverse the path
This only works for unweighted graphs because every edge has the same "cost" (1 hop). With weighted graphs, BFS won't necessarily find the shortest path by distance or cost—you'd need different algorithms like Dijkstra's.
Key Takeaway: BFS naturally computes shortest paths in unweighted graphs by tracking distances and parent pointers during traversal; reconstruct any path by following parents backward from the destination.