Shortest Path in a Graph
External
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/ZAaJA/bfs-and-shortest-paths
- 5 Ways to Find the Shortest Path in a Graph https://betterprogramming.pub/5-ways-to-find-the-shortest-path-in-a-graph-88cfefd0030f
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. 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.
⚠️ Only breadth-first search gives the guarantee of the shortest path.
TODO
Reshape this page to accommodate Dijkstra's Algorithm.
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.