I want to know the time-complexity of a bidirectional Dijkstra algorithm.
A normal Dijkstra using a Min-Heap has O(n log n + m). My guess would be that the Bidirectional stays same. However Wikipedia suggests
that the improvement of Bidirectional Search in general can be expressed in O-Notation.
Is this possible to calculate for the bidirectional Dijkstra as well and how?
Basically the bidirectional approach cost twice the monodirectional processing of a half-sized graph . For brute-force exponential algorithms that's a huge gain (from O(mn) to O(2*(mn/2)).
For Djikstra, the worst case remains basically the same.
However, time complexity is maybe not the best metric to assess efficiency here.
In practical cases like finding a route on a road network, bidirectional approach is akin to growing a disc around each end and stop (nearly) as soon as both discs meet, while a single-direction approach would require to grow a disc from the start until you reach the end.
Intuitively, if R is the straight distance between start and end, the cost of a straigth search would be O(R2), while the bidirectional approach would be in O(2*(R/2)2), i.e. 2 times faster.
this paper covers the topic pretty well.
And at any rate, A* is basically the way to go unless you're exploring a search space where no efficient estimate heuristic is available.
