Shortest Path with Bidirectional Search: Difference between revisions
(Created page with "=Internal= * Shortest Path in a Graph") |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[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= | |||
Bidirectional search can be used to find the shortest path between a source and a destination node. It operates by running two simultaneous breadth-first searches, one from each node. When their searches collide, we have found the shortest path. This algorithm is faster than the [[Breadth-First_Search-based_Shortest_Path_Algorithm|classic breadth-first search based shortest path]]. | |||
For a justification, consider a graph where every node has at most k adjacent nodes, and the shortest path from node s to node t has length d. For the classic breadth-first search algorithm, we visit k nodes at step 1, k<sup>2</sup> nodes at step 2, etc. For a path with length d, we visit k + k<sup>2</sup> + ... + k<sup>d</sup>. | |||
In case of bidirectional search, the searches collide after approximately d/2 levels, at mid point. The searches visit 2 (k + k<sup>2</sup> + ... + k<sup>d/2</sup>). | |||
Latest revision as of 20:43, 9 November 2021
Internal
Overview
Bidirectional search can be used to find the shortest path between a source and a destination node. It operates by running two simultaneous breadth-first searches, one from each node. When their searches collide, we have found the shortest path. This algorithm is faster than the classic breadth-first search based shortest path.
For a justification, consider a graph where every node has at most k adjacent nodes, and the shortest path from node s to node t has length d. For the classic breadth-first search algorithm, we visit k nodes at step 1, k2 nodes at step 2, etc. For a path with length d, we visit k + k2 + ... + kd.
In case of bidirectional search, the searches collide after approximately d/2 levels, at mid point. The searches visit 2 (k + k2 + ... + kd/2).