Responsive Ad Area

Share This Post

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}

Share This Post

Leave a Reply

Your email address will not be Publishedd. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Skip to toolbar