Dijkstra's algorithm spp

  • #1
141
6

Main Question or Discussion Point


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?
 

Answers and Replies

  • #2
I like Serena
Homework Helper
6,577
176

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 Erenjaeger

Related Threads on Dijkstra's algorithm spp

Replies
2
Views
604
Replies
2
Views
526
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
430
  • Last Post
Replies
2
Views
858
  • Last Post
Replies
4
Views
766
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
2
Replies
26
Views
18K
  • Last Post
Replies
1
Views
2K
Top