Dijkstra Algorithm
Also known as: Dijkstra's algorithm, shortest path algorithm
Dijkstra's Algorithm, introduced by Edsger W. Dijkstra in 1956, is one of the most fundamental algorithms in computer science for solving the single-source shortest path problem. It finds the shortest path from a starting vertex to all other vertices in a weighted graph with non-negative edge weights.
Key highlights
- Simple to understand and implement with clear correctness guarantees
- Efficient with proper data structures: O((V+E)logV) with binary heap, O(V²) with array
- Optimal for non-negative weight graphs; proves optimality of computed paths
- Works on both directed and undirected graphs
- Foundation for numerous extensions and related algorithms
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Apply Dijkstra's algorithm when finding shortest paths in graphs with non-negative edge weights. It is ideal for navigation systems, network routing, and any graph problem requiring optimal paths. Use it for single-source shortest paths to all vertices. For graphs with negative weights, use Bellman-Ford instead. For bidirectional search or heuristic guidance, consider A* algorithm.
Strengths & limitations
- Simple to understand and implement with clear correctness guarantees
- Efficient with proper data structures: O((V+E)logV) with binary heap, O(V²) with array
- Optimal for non-negative weight graphs; proves optimality of computed paths
- Works on both directed and undirected graphs
- Foundation for numerous extensions and related algorithms
- Cannot handle graphs with negative edge weights
- Computes shortest paths to all vertices, not just one destination (though can terminate early)
- Less efficient than A* when heuristic information is available
- Requires all vertices to be discovered; inefficient for very sparse connectivity
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
Why does Dijkstra's algorithm fail on negative weights?
The algorithm assumes that once a vertex is finalized, no shorter path can be found through unvisited vertices. With negative weights, a longer path might later improve when a negative edge is used, violating this assumption.
What data structure should be used for the priority queue?
Binary heaps provide O(logV) operations for both insertion and extraction, resulting in O((V+E)logV) total complexity. Fibonacci heaps achieve O(E+VlogV) but have large constant factors. Arrays work well for small graphs.
How can Dijkstra's algorithm find the path to one specific destination?
Terminate the algorithm as soon as the destination vertex is selected (its distance is finalized), avoiding unnecessary computation. Alternatively, reconstruct the path by maintaining parent pointers during execution.
Can Dijkstra's algorithm be used in undirected graphs?
Yes, undirected graphs can be represented as directed graphs with edges in both directions for each undirected edge, each with the same weight. The algorithm works identically on the bidirectional representation.
Sources
- 1.Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
- 2.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.ISBN 978-0-262-03384-8
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Dijkstra Algorithm. ScholarGate. https://scholargate.app/operations-research/dijkstra-algorithm