Course contentsShow
← Computer Science
Lesson 699 of 2,87217. Graph Traversal AlgorithmsFree lesson

Shortest Path in Unweighted Graphs

Using BFS to find shortest paths: tracking distances from source, parent pointers, and path reconstruction.

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:

  1. Distance from source to each vertex
  2. Parent pointers: which vertex led us to each node
  3. 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] + 1
    • parent[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.