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
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
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
- 37,487
- 14,377
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.