# Understanding Correctness of Bidirectional Dijkstra

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!

• 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. Commented May 14, 2019 at 1:33
• @BearAqua I've added an answer with a proof that is easier to understand! Commented May 20, 2019 at 17:30

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!