Finds shortest paths from source to all vertices in weighted graphs
Time: O((V + E) log V)
Space: O(V)
Use Case: GPS navigation, network routing, shortest path problems
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Dijkstra's Algorithm
Dijkstra's algorithm computes the shortest path from a source node to every other node in a weighted graph with non-negative edge weights. Published by Edsger Dijkstra in 1959, it remains the standard single-source shortest path algorithm and the basis of most practical routing systems.
How it works
The algorithm maintains a tentative distance for every node, initially infinite except the source at zero. Using a priority queue it repeatedly extracts the unsettled node with the smallest tentative distance, marks it final, and relaxes each outgoing edge: if the path through the current node is shorter than the neighbor's recorded distance, the distance is updated. With a binary heap this runs in O((V + E) log V) time. Non-negative weights are essential; a negative edge can invalidate already settled nodes.
Applications
Dijkstra's algorithm drives GPS navigation, internet routing protocols such as OSPF, flight and transit planners, and network latency analysis. It also appears inside games for pathfinding when heuristics are unavailable. In interviews it is the canonical answer for weighted shortest path questions and the starting point for discussing A* and Bellman-Ford trade-offs.