Huumah
- 27
- 0
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
Bidirectional Search (graph theory)
- Thread starter Huumah
- Start date
-
- Tags
- Graph theory Search Theory
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
1 reply · 3K views
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
Discussion
Mentor
- 37,533
- 14,418
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.
The fact that there are no shorter paths looks trivial then.