Is A→E→D→F a valid solution for Dijkstra's algorithm?

  • Context: Undergrad 
  • Thread starter Thread starter Erenjaeger
  • Start date Start date
  • Tags Tags
    Algorithm
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 · 1K views
Erenjaeger
Messages
141
Reaction score
6


In this video the solution is: A→B→D→F
but the paths A→B→D and A→E→D both have a distance of 9, so when you get to D you can either have [B,9] or [E,9] where the first entry is the predecessor and the second entry is the 'cost' on that path so far, or here the distance.
is the solution A→E→D→F also correct or is there some reason that he chose the path A→B→D→F?
 
Physics news on Phys.org
Erenjaeger said:


In this video the solution is: A→B→D→F
but the paths A→B→D and A→E→D both have a distance of 9, so when you get to D you can either have [B,9] or [E,9] where the first entry is the predecessor and the second entry is the 'cost' on that path so far, or here the distance.
is the solution A→E→D→F also correct or is there some reason that he chose the path A→B→D→F?


Hi Erenjaeger! :)

Yes, A→E→D→F is also correct.
The only reason to pick A→B→D is just because it was evaluated earlier, and A→E→D does not improve on it.
It seems that this decision was skipped in the explanation in the video.
 
  • Like
Likes   Reactions: Erenjaeger