Question

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!

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top