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.