HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the "Bidirectional Dijkstra" algorithm optimal?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#53943, answer score: 4

Revisions (0)

No revisions yet.