Dijkstra's algorithm - Shortest Path Query

In summary, when faced with a choice between two nodes that have equal value, you should pick one as the current node and the other will be the current node in the next cycle. There is no way of knowing beforehand which one will be the shortest.
  • #1
binbagsss
1,254
11
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
  • #2
You pick one of them as the current node. The other will be the current node in the next cycle.
 
  • Like
Likes binbagsss
  • #3
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 :)
 

1. What is Dijkstra's algorithm and what does it do?

Dijkstra's algorithm is a popular algorithm used to find the shortest path between two nodes in a graph. It calculates the shortest distance from a starting node to all other nodes in the graph, taking into account the weight of each edge. The algorithm is commonly used in navigation and routing applications.

2. How does Dijkstra's algorithm work?

Dijkstra's algorithm works by maintaining a list of unvisited nodes and their current shortest distance from the starting node. It then selects the node with the shortest distance and checks its neighboring nodes. If the distance to a neighboring node can be improved by going through the selected node, the distance is updated. This process is repeated until all nodes have been visited and the shortest distance to each node has been determined.

3. What is the time complexity of Dijkstra's algorithm?

The time complexity of Dijkstra's algorithm is O(V^2), where V is the number of vertices in the graph. This means that the algorithm will take longer to run on larger graphs with more vertices.

4. Can Dijkstra's algorithm handle negative edge weights?

No, Dijkstra's algorithm cannot handle negative edge weights. This is because the algorithm relies on the assumption that the shortest path to a node will not change once it has been visited. Negative edge weights can cause the algorithm to get stuck in a loop and produce incorrect results.

5. Are there any alternative algorithms to Dijkstra's algorithm for finding shortest paths?

Yes, there are several alternative algorithms such as the Bellman-Ford algorithm and the A* search algorithm. These algorithms have different time complexities and may be more suitable for certain types of graphs or applications.

Similar threads

MHB Finding Shortest Path in G: Dijkstra's Algorithm
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
    • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
MHB Show that the Dijkstra's algorithm computes correctly the shortest paths
    • Programming and Computer Science
Replies
1
Views
1K
Dijkstra's algorithm: choosing which point to begin with
    • Programming and Computer Science
Replies
4
Views
1K
Djikstra's algorithm with distance 1 between every node
    • Programming and Computer Science
Replies
4
Views
1K
I Gradient descent algorithm and optimizers
    • General Math
Replies
5
Views
844
Optimal Path from source to multiple destinations
    • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
MHB Calculate the diameter of a tree
    • Set Theory, Logic, Probability, Statistics
Replies
11
Views
3K
MHB Finding a Minimal Vertex Cover & Max Sets for a Graph
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Shortest path to a point that doesn't pass through the given circle
    • Precalculus Mathematics Homework Help
Replies
5
Views
1K

Hot Threads

Recent Insights

Back
Top