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
Click For Summary
SUMMARY

The discussion confirms that both paths A→B→D→F and A→E→D→F are valid solutions for Dijkstra's algorithm, as they both yield the same distance of 9 to node D. The preference for A→B→D→F in the video is attributed to its earlier evaluation rather than any inherent superiority. The choice of path does not affect the overall cost, and the explanation in the video overlooked this detail.

PREREQUISITES
  • Understanding of Dijkstra's algorithm
  • Familiarity with graph theory concepts
  • Knowledge of pathfinding algorithms
  • Basic programming skills for algorithm implementation
NEXT STEPS
  • Study the implementation of Dijkstra's algorithm in Python
  • Explore alternative pathfinding algorithms like A* and Bellman-Ford
  • Learn about graph data structures and their applications
  • Investigate the impact of path evaluation order on algorithm performance
USEFUL FOR

Computer science students, software developers, and anyone interested in algorithm optimization and graph theory.

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

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
Replies
3
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 0 ·
Replies
0
Views
2K
  • · Replies 11 ·
Replies
11
Views
4K
  • · Replies 18 ·
Replies
18
Views
3K
  • · Replies 1 ·
Replies
1
Views
4K
  • · Replies 0 ·
Replies
0
Views
4K