Breadth-First Search-based Shortest Path Algorithm: Difference between revisions
Jump to navigation
Jump to search
(Created page with "=Internal= * Shortest Path in a Graph =Overview=") |
|||
| Line 2: | Line 2: | ||
* [[Shortest_Path_in_a_Graph#Shortest_Path_Algorithms|Shortest Path in a Graph]] | * [[Shortest_Path_in_a_Graph#Shortest_Path_Algorithms|Shortest Path in a Graph]] | ||
=Overview= | =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. | |||
Revision as of 19:19, 14 October 2021
Internal
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.