2
$\begingroup$

I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10:

https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf

For a contradiction, they consider an $s-t$ path $p$ that is shorter than the minimum sum $\mu$ of tentative distances from the forward and backward search.
The next step I don't understand: there is an edge $(v,w)$ on this path, such that:

  1. $dist(s,v) < top_f$
  2. $dist(w,t) < top_b$

Where do these relationships come from?

From what I see, after stopping, it holds that $\mu \leq top_f + top_b$.

So if we consider any edge $(v,w)$ of $p$, we have that

$dist(s,v) + length(v,w) + dist(w,t) < top_f + top_b$

We can leave out that edge to get the inequality

$dist(s,v) + dist(w,t) < top_f + top_b$

But from this, I can't derive these two relationships.

I appreciate any help! Thanks!

$\endgroup$
  • $\begingroup$ Here's some thought: Consider the order of removal of distances from the min-heap - smaller partial distances are removed first. Then if $\text{dist}(s,v)>top_f$, $top_f$ would have been removed first, which results in a contradiction. $\endgroup$ – BearAqua May 14 at 1:33
  • $\begingroup$ @BearAqua I've added an answer with a proof that is easier to understand! $\endgroup$ – krueger_fl May 20 at 17:30
0
$\begingroup$

I came across these slides where on slide 23 another proof is given, however the idea of this proof is the same as in the slides of my original post.

enter image description here

But this still doesn't show, why $dist(s,v)$ and $dist(w,t)$ need to be less than $top_f$ and $top_b$ respectively.

EDIT: Note that with this proof $dist(s,v) \leq top_f$ and $dist(w,t) \leq top_b$ hold, since both vertices have already been settled. I'm in doubt, whether the original statement $dist(s,v) < top_f$ and $dist(w,t) < top_b$ is actually correct and therefore I'm marking this question as 'answered'. However if anyone finds an explanation, feel free to answer!

$\endgroup$

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.