Understanding Correctness of Bidirectional Dijkstra
-
05-11-2019 - |
Question
I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10:
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:
- $dist(s,v) < top_f$
- $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