User:Jeshaan/sandbox: Difference between revisions – Wikipedia

This is the user sandbox of Jeshaan. A user sandbox is a subpage of the user’s user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here. Other sandboxes: Main sandbox | Template sandbox Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

A common variant of Dijkstra’s algorithm for single-source–single-target queries is the bidirectional Dijkstra method.
Instead of growing the search frontier only from the source vertex s, it runs two simultaneous searches: one forward from s on the original graph and one backward from the target vertex t on the graph with edges reversed.
The two frontiers advance toward each other and typically meet somewhere along the shortest s–t path.

Each search maintains its own priority queue of tentative distance labels.
At each step, the algorithm expands the frontier whose current minimum label is smaller.
It keeps track of the length μ of the best complete s–t path found so far, and it stops when the sum of the smallest keys in both queues is at least μ — meaning that no yet-undiscovered path can be shorter.

Because the frontiers meet roughly in the middle, the algorithm often scans far fewer vertices and edges than a one-directional search.
This makes it popular for large road-network graphs and other applications in point-to-point routing.
Bidirectional Dijkstra is also a standard building block for further speed-up techniques such as A*-based landmark routing (ALT), reach-based routing, and contraction hierarchies.