# Dijkstra's algorithm - Shortest Path Query

• I
• binbagsss
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.
binbagsss
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.

You pick one of them as the current node. The other will be the current node in the next cycle.

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 :)

## 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.

• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
4
Views
1K
• Programming and Computer Science
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
• Programming and Computer Science
Replies
4
Views
1K
• General Math
Replies
2
Views
643
• Quantum Physics
Replies
1
Views
984
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Programming and Computer Science
Replies
1
Views
1K