Dijkstra's algorithm - Shortest Path Query

  • Context: Undergrad 
  • Thread starter Thread starter binbagsss
  • Start date Start date
  • Tags Tags
    Algorithm Path
Click For Summary
SUMMARY

Dijkstra's algorithm is utilized for finding the shortest path in a graph. When faced with a choice between two nodes that both have the minimal value, the algorithm allows for selecting one node as the current node while the other remains available for the next iteration. This process continues until the shortest path is determined. The discussion confirms that there is no need to evaluate both nodes simultaneously; instead, one can be chosen and revisited in subsequent cycles.

PREREQUISITES
  • Understanding of graph theory concepts
  • Familiarity with Dijkstra's algorithm
  • Basic knowledge of algorithmic complexity
  • Experience with programming languages that implement Dijkstra's algorithm, such as Python or Java
NEXT STEPS
  • Study the implementation of Dijkstra's algorithm in Python using libraries like NetworkX
  • Explore variations of Dijkstra's algorithm, such as Bidirectional Dijkstra
  • Learn about A* search algorithm for pathfinding
  • Investigate the impact of graph data structures on the performance of Dijkstra's algorithm
USEFUL FOR

Computer scientists, software developers, and data analysts interested in graph algorithms and pathfinding techniques.

binbagsss
Messages
1,291
Reaction score
12
Hi,

I am just wondering what you should do in the case that you have a choice between two nodes to include for the next step, i..e both are equal to the minimal value of the set under consideration

Do you need to follow through both cases and then see which way is the shortest, or is there a way of knowing beforehand?

Many thanks.
 
Physics news on Phys.org
You pick one of them as the current node. The other will be the current node in the next cycle.
 
  • Like
Likes   Reactions: binbagsss
Orodruin said:
You pick one of them as the current node. The other will be the current node in the next cycle.
ahh makes sense ! thank you :)
 

Similar threads

MHB Finding Shortest Path in G: Dijkstra's Algorithm
  • · Replies 2 ·
Replies
2
Views
2K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
  • · Replies 4 ·
Replies
4
Views
2K
Dijkstra's algorithm: choosing which point to begin with
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Question about Grover's algorithm
  • · Replies 1 ·
Replies
1
Views
2K
Optimal Path from source to multiple destinations
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Gradient descent algorithm and optimizers
  • · Replies 5 ·
Replies
5
Views
2K
Shortest path to a point that doesn't pass through the given circle
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Shortest path problem with multiple goals on a grid
  • · Replies 2 ·
Replies
2
Views
2K
MHB Calculate the diameter of a tree
  • · Replies 11 ·
Replies
11
Views
3K
Shortest path finding algorithms
  • · Replies 2 ·
Replies
2
Views
2K