Shortest Paths in Unweighted Digraphs

There are some applications where BFS can be used as a substitute for DFS (for example, in detecting bipartite graphs or the Ford-Fulkerson algorithm covered in a later chapter). However, there are other applications that work exclusively with only one of the two search algorithms. For example, BFS cannot be used as a substitute for Tarjan’s algorithm. On the other hand, unlike DFS, BFS can be used directly for finding the shortest paths in unweighted graphs and digraphs.

In this lesson, we’d like to show that a breadth-first tree of an unweighted digraph represents a tree of all shortest paths from the root to all other vertices. Recall that the length of a path in an unweighted digraph is just the number of edges in the path.

Note: The definitions of shortest paths and the discussion in this lesson apply equally well to unweighted graphs. But for convenience, we focus our attention on unweighted digraphs.

BFS for finding shortest paths

Given an unweighted digraph $G$, we want to show that a shortest $r-v$ path in $G$ corresponds to the $r-v$ path in a breadth-first tree of $G$ that’s rooted at $r$. This may be rephrased more precisely as follows:

For any shortest path from a vertex $r$ to $v$ in $G$, the length of the path is the same as the depth of $v$ in any breadth-first tree of $G$.

There’s a simple reason for this. Let’s pause and think about it.

Suppose a shortest path from $r$ to $v$ in $G$ ...