Shortest Path in a Graph: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
No edit summary
Line 9: Line 9:


⚠️ Only breadth-first search gives the guarantee of the shortest path.
⚠️ Only breadth-first search gives the guarantee of the shortest path.
=Algorithm=


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

Revision as of 23:05, 1 October 2021

External

Internal

Overview

The BFS algorithm as described above can be used, with a very small constant-time addition, to keep track of the layer each newly discovered node is in, relative to the start node, and that will automatically indicate the shortest path between the start node s and a reachable node v.

⚠️ Only breadth-first search gives the guarantee of the shortest path.

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.

BFS Layers.png