Responsive Ad Area

test

# 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:

• dist(s,v) < top_f
• dist(w,t) < top_r

Where do these relationships come from?

From what I see, after stopping, it holds that mu <= top_r + top_f.

So if we consider any edge (v,w) of p, we have that dist(s,v) + length(v,w) + dist(w,t) <= top_r + top_f. We can leave out that edge to get the inequality dist(s,v) + dist(w,t) <= top_r + top_f.

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

I appreciate any help! Thanks!

Understanding Correctness of Bidirectional Dijkstra
Understanding Correctness of Bidirectional Dijkstra
test
{\$excerpt:n}

Skip to toolbar