patternMinor
Is the "Bidirectional Dijkstra" algorithm optimal?
Viewed 0 times
thedijkstraoptimalalgorithmbidirectional
Problem
In some sites they say the bidirectional Dijkstra's algorithm is optimal, e.g.,
this, and this. Also there is some software that uses this algorithm (for example this DBMS).
But some posts express doubts about the optimality of this algorithm, such this, and this. Which one is correct? Is the bidirectional Dijkstra's algorithm optimal or not?
this, and this. Also there is some software that uses this algorithm (for example this DBMS).
But some posts express doubts about the optimality of this algorithm, such this, and this. Which one is correct? Is the bidirectional Dijkstra's algorithm optimal or not?
Solution
When we talk about the "bidirectional Dijkstra" algorithm, we actually mean a family of similar algorithms which are implementations of a more abstract idea. All of these algorithms are optimal (produce an optimal solution). Some algorithms may work only under some assumptions on the input, for example only in the unweighted case, which is what the doubtful posts seem to have in mind.
More generally, algorithms usually come with correctness proofs. These proofs show that under certain conditions, the algorithm has certain guarantees. If these conditions don't hold, that the guarantees don't necessarily hold. When using an algorithm, check that the conditions that you know hold indeed imply the guarantees that you are looking for.
More generally, algorithms usually come with correctness proofs. These proofs show that under certain conditions, the algorithm has certain guarantees. If these conditions don't hold, that the guarantees don't necessarily hold. When using an algorithm, check that the conditions that you know hold indeed imply the guarantees that you are looking for.
Context
StackExchange Computer Science Q#53943, answer score: 4
Revisions (0)
No revisions yet.