1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bidirectional Search (graph theory)

  1. May 27, 2015 #1

    Attempt at solution
    This is an old exam question. Am I correct to say the shortest path goes through M since M is in d(O,M) and d(D,M)?
    I don't know how to prove this and answer the question about the cost
  2. jcsd
  3. May 29, 2015 #2


    User Avatar
    2017 Award

    Staff: Mentor

    With some assumption about the search algorithm (i. e. one that does not miss nodes with smaller costs - check this), you are right.
    The fact that there are no shorter paths looks trivial then.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted