5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ A question to ask yourself: optimal in which sense? $\endgroup$ – Raphael Mar 3 '16 at 17:43
  • $\begingroup$ @Raphael Optimal when it outputs the shortest path not generate near-optimal solution in some cases. in my comment to Mr. "Yuval Filmus" answer, I mentioned an example. $\endgroup$ – moksef Mar 3 '16 at 17:48
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Consider this simple graph (with nodes A,B,C,D,E). The edges of this graph and their weights are: "A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1". when I use Dijkstra algorithm for this graph in both sides: in forward it finds B after A and then D, in backward it finds C after E and then D. in this point, both sets have same vertex and an intersection. Does this is the termination point or It must be continued? because this answer (A->D->C->E) is incorrect. How can I find the termination of algorithm? $\endgroup$ – moksef Mar 3 '16 at 17:15
  • 3
    $\begingroup$ Unfortunately I'm not aware of the details of "bidirectional Dijkstra". Find a source which quotes the algorithm together with a correctness statement (preferably a correctness proof, which you won't have to read but increases the probability that the statement is correct). $\endgroup$ – Yuval Filmus Mar 3 '16 at 17:17
  • 1
    $\begingroup$ For a good termination condition, please refer to cs.princeton.edu/courses/archive/spr06/cos423/Handouts/…, where they suggest the correct stopping condition is that the sum of the values at the top of each heap (forward and reverse) >= the length of the shortest path seen so far. Once that condition holds, the shortest path seen so far is the shortest path. Correctness statement is on slide 10. $\endgroup$ – Erick G. Hagstrom Mar 4 '16 at 0:22
  • $\begingroup$ google.com/… sees it slightly differently, in two phases. Phase I terminates when a single vertex has been scanned both forward and backward. Phase II then searches for the shortest path by eliminating vertices. $\endgroup$ – Erick G. Hagstrom Mar 4 '16 at 0:28
  • 2
    $\begingroup$ Bottom line: you can't just assume that the shortest path goes through the first vertex you find going both forwards and backwards. $\endgroup$ – Erick G. Hagstrom Mar 4 '16 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.