- #1
yakin
- 42
- 0
How to figure out the shortest path using dijkstra algorithm?
In summary, the Dijkstra algorithm is a well-known algorithm used to find the shortest path between two nodes in a graph. It works by maintaining a list of unvisited nodes, assigning a tentative distance to each node, and then iteratively updating the tentative distances until the shortest path is found. The time complexity of the algorithm is O(V^2), where V is the number of vertices in the graph. It cannot handle negative edge weights and relies on a greedy approach to determine the shortest path. While it can handle graphs with cycles, the presence of cycles may lead to incorrect calculations. Other shortest path algorithms, such as Bellman-Ford or Floyd-Warshall, use different strategies to find the shortest path.
- #2
Nono713
Gold Member
MHB
- 618
- 4
What have you tried? What are your thoughts on the problem, are you stuck somewhere? Could you please show a minimum of effort in your questions? 
- #3
yakin
- 42
- 0
Bacterius said:What have you tried? What are your thoughts on the problem, are you stuck somewhere? Could you please show a minimum of effort in your questions?
Actually, i have done my work. Just wanted to know if it is correct. Here is an image of my work.View attachment 2437
Attachments
Last edited:
FAQ: How to figure out the shortest path using dijkstra algorithm?
What is the Dijkstra algorithm and how does it work?
The Dijkstra algorithm is a well-known algorithm used to find the shortest path between two nodes in a graph. It works by maintaining a list of unvisited nodes, assigning a tentative distance to each node, and then iteratively updating the tentative distances until the shortest path is found.
What is the time complexity of the Dijkstra algorithm?
The time complexity of the Dijkstra 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.
How does the Dijkstra algorithm handle negative edge weights?
The Dijkstra algorithm cannot handle negative edge weights because it relies on selecting the shortest path by always choosing the smallest tentative distance. If there are negative edge weights, this may lead to incorrect shortest path calculations.
What is the difference between Dijkstra algorithm and other shortest path algorithms?
The main difference between Dijkstra algorithm and other shortest path algorithms is the way they determine the shortest path. Dijkstra's algorithm uses a greedy approach, always choosing the path with the smallest tentative distance. Other algorithms, such as Bellman-Ford or Floyd-Warshall, use different strategies to find the shortest path.
Can the Dijkstra algorithm handle graphs with cycles?
Yes, the Dijkstra algorithm can handle graphs with cycles. However, the presence of cycles may lead to incorrect shortest path calculations, so the graph must be acyclic for the algorithm to work correctly.