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.

Stopping on Target and Keeping the Path

The previous algorithm calculates the shortest distance from s to any nodes in the graph.

Most typically, we want to find out the shortest path distance from a specific target node, and possibly to report the path to the user. For that, the algorithm should be modified as follows:

BFS_with_Shortest_Path(graph G, start vertex s, target vertex t)
  # 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
        if w == t:
           # We reached the target, exit the function, the graph 
           # is annotated with information that allows us to backtrack and find the path
           return;
        else:
          add w to Q
        fi

To find one of the actual shortest path (there might be equivalent paths with the same length, for undirected graphs start from the target and walk back the edges looking for the node(s) with the immediately smaller distance until reaching 0. For directed graphs, invert the edge direction and do the same thing.

Backtrack_Shortest_Path_Undirected(graph G, target vertex t)
initialize list L
add t to L
v = t
while true:
  for every edge (v, u):
    if u.distance = v.distance - 1:
      add u to L 
      if u.distance == 0: # We reached the source, exit
        return L
      v = u
      break # the for loop

To print the path, walk L backwards.