Shortest Path with Bidirectional Search: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
(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).