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.

A faster breadth-first search shortest path algorithm is Shortest Path with Bidirectional Search.

Algorithm

The algorithm is (differences to the canonical BFS algorithm are emphasized):

BFS_with_Shortest_Path(graph G, start vertex s)
  # All nodes are assumed unexplored
  initialize a Queue Q (FIFO)
  mark s as explored
  annotate s with distance 0
  place s in Q
  while Q has elements
    remove the head of the queue v
    for each edge (v, w):
      if w unexplored:
        mark w as explored
        annotate w with a distance dist(w) = dist(v) + 1
        add w to Q

The distance computed on reachable node gives the "layer" and the distance from the start node s.