Breadth-First Search-based Shortest Path Algorithm

Internal

• Shortest Path in a Graph

Overview

The BFS-based algorithm as described above can be used, with a very small constant-time addition, to keep track of the layer of each newly discovered node, relative to the start node, and that will automatically indicate the shortest path between the start node s and a reachable node v. It works by annotating the start vertex with 0 and then annotating each new node with D + 1, where D is the distance of the node we discovered the new node from.

The BFS-based shortest path algorithm works with both directed and undirected graphs.

⚠️ Only breadth-first search gives the guarantee of the shortest path, depth-first search will not provide this guarantee.