What Is Dijkstra’s Algorithm?
Dijkstra’s algorithm, published by Edsger W. Dijkstra in 1959, solves the single-source shortest path problem: given a weighted graph and a starting node, find the minimum-cost path from that node to every other node in the graph.
The algorithm works by maintaining a set of visited nodes and a distance table. At each step it picks the unvisited node with the smallest known distance, visits it, and updates the distances of its neighbors. This greedy strategy guarantees that when a node is visited, its shortest distance has been found.
Input: A weighted directed or undirected graph G = (V, E) with non-negative edge weights, and a source vertex s ∈ V.
Output: For each vertex v ∈ V, the shortest-path distance d(s, v) and the predecessor on the shortest path from s to v.
The key constraint is that edge weights must be non-negative. If your graph has negative weights, you need Bellman-Ford instead. We’ll cover why at the end of the article.
How It Works — The Core Idea
The algorithm maintains three things at all times:
- A distance table — the current best known distance from the source to each node, initialized to ∞ for all nodes except the source (which starts at 0)
- A visited set — nodes whose shortest distance has been finalized and won’t change
- A predecessor table — for each node, which node comes before it on the current shortest path (used to reconstruct the actual path)
Each iteration follows the same three steps: pick the unvisited node with the smallest distance, mark it as visited, then update (relax) the distances of all its unvisited neighbors.
The key insight is that when a node is removed from the priority queue (visited), its distance is already minimal. This is because all edge weights are non-negative — no future path through unvisited nodes can improve the distance of an already-visited node. This is the guarantee that makes the greedy approach correct.
Pseudocode
Here is the standard implementation using a min-priority queue (min-heap). This is the version you’ll see in most textbooks and interviews.
Lines 16–19 are the relaxation step — the heart of the algorithm. Every time we visit a node, we check whether going through it offers a shorter route to each neighbor. If it does, we update the distance and predecessor.
Full Worked Example
Let’s trace through the algorithm on a concrete graph. We’ll use a 6-node undirected weighted graph and find all shortest paths from node A.
The edges are: A–B(4), A–C(2), B–C(7), B–D(5), B–E(11), C–E(3), D–F(2), E–F(5). We want all shortest paths from A.
Step-by-step walkthrough
B: dist[A] + w(A,B) = 0 + 4 = 4 < ∞ → update dist[B] = 4, prev[B] = A
C: dist[A] + w(A,C) = 0 + 2 = 2 < ∞ → update dist[C] = 2, prev[C] = A
B: dist[C] + w(C,B) = 2 + 7 = 9 > 4 → no update (current path A→B = 4 is better)
E: dist[C] + w(C,E) = 2 + 3 = 5 < ∞ → update dist[E] = 5, prev[E] = C
D: dist[B] + w(B,D) = 4 + 5 = 9 < ∞ → update dist[D] = 9, prev[D] = B
E: dist[B] + w(B,E) = 4 + 11 = 15 > 5 → no update (A→C→E = 5 is better)
F: dist[E] + w(E,F) = 5 + 5 = 10 < ∞ → update dist[F] = 10, prev[F] = E
F: dist[D] + w(D,F) = 9 + 2 = 11 > 10 → no update (path via E is better at 10)
Complete trace table
Here is the full distance table for every iteration. ✓ marks the node visited in each round. Orange values were updated in that round.
| Iteration | Visit | dist[A] | dist[B] | dist[C] | dist[D] | dist[E] | dist[F] |
|---|---|---|---|---|---|---|---|
| Init | — | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | A ✓ | 0 | 4 | 2 | ∞ | ∞ | ∞ |
| 2 | C ✓ | 0 | 4 | 2 | ∞ | 5 | ∞ |
| 3 | B ✓ | 0 | 4 | 2 | 9 | 5 | ∞ |
| 4 | E ✓ | 0 | 4 | 2 | 9 | 5 | 10 |
| 5 | D ✓ | 0 | 4 | 2 | 9 | 5 | 10 |
| 6 | F ✓ | 0 | 4 | 2 | 9 | 5 | 10 |
Final shortest paths from A
Reading the predecessor table, the shortest paths are:
- A → B: A → B, cost 4
- A → C: A → C, cost 2
- A → D: A → B → D, cost 9
- A → E: A → C → E, cost 5 (NOT A → B → E which costs 15)
- A → F: A → C → E → F, cost 10 (NOT through D which costs 11)
Notice that the path to E goes through C, not B — even though B is “closer” as a single hop. The algorithm correctly found that the route via C is cheaper overall.
Time and Space Complexity
The complexity of Dijkstra’s algorithm depends on the data structure used for the priority queue.
| Implementation | ExtractMin | DecreaseKey | Total Time | Notes |
|---|---|---|---|---|
| Array (linear scan) | O(V) | O(1) | O(V²) | Simple; good for dense graphs |
| Binary heap | O(log V) | O(log V) | O((V + E) log V) | Standard implementation; good for sparse graphs |
| Fibonacci heap | O(log V) amortized | O(1) amortized | O(E + V log V) | Theoretically optimal; complex to implement |
In practice, the binary heap version — O((V + E) log V) — is what you’ll see in most real implementations and what interviewers expect. For dense graphs where E ≈ V², the simple O(V²) array version can actually be faster in practice due to lower constants.
Space complexity is O(V + E) for storing the graph plus O(V) for the distance and predecessor arrays — O(V + E) total.
Why Dijkstra’s Fails with Negative Weights
The greedy invariant — “when a node is extracted from the queue, its distance is final” — breaks down completely if edge weights can be negative.
Consider a graph: A→B (weight 5), A→C (weight 2), C→B (weight −4). Dijkstra visits B first with distance 5 from A, marks it final. Later it visits C (dist 2) and discovers path A→C→B = 2 + (−4) = −2, which is shorter — but B is already finalized. Dijkstra misses the correct answer.
If your graph has negative weights (but no negative cycles), use Bellman-Ford, which runs in O(VE) and handles negative weights correctly. If there are negative cycles, shortest paths are undefined (you can keep going around the cycle to decrease cost forever).
Dijkstra’s vs Bellman-Ford
| Property | Dijkstra’s | Bellman-Ford |
|---|---|---|
| Negative weights | ✗ Not supported | ✓ Supported |
| Negative cycles | ✗ Incorrect result | ✓ Detects them |
| Time complexity | O((V+E) log V) | O(VE) |
| Best for | Sparse graphs, GPS, routing | Currency arbitrage, networks with negative costs |
| Strategy | Greedy (priority queue) | Dynamic programming (V−1 passes) |
| Single source | ✓ | ✓ |
Real-World Applications
Dijkstra’s algorithm underpins a surprising range of real systems:
- GPS navigation — finding the shortest driving route between two points on a road network, where edge weights are travel times or distances
- Network routing (OSPF) — the Open Shortest Path First protocol, used by routers on the internet, uses Dijkstra’s to compute optimal forwarding tables
- Flight booking systems — finding cheapest or fastest flight routes through a graph of airports and connections
- Robotics path planning — navigating through a discretized map where nodes are grid cells and edge weights encode terrain costs
- Social networks — computing degrees of separation between users (with unit weights)
Common Mistakes on Exams
Not updating the predecessor correctly
When you update a distance, you must also update prev[v]. A common error is updating the distance but forgetting the predecessor — which makes it impossible to reconstruct the actual path even though the distances are correct.
Revisiting already-visited nodes
Once a node is extracted from the priority queue and marked visited, never process it again, even if you see it in the queue with a different distance. In practice this means: when you extract a node, check if it’s already been visited and skip if so.
Confusing directed and undirected graphs
In an undirected graph, every edge (u, v, w) must be represented in both directions. If you only add the edge in one direction you’ll get asymmetric results that look inexplicably wrong.
Using Dijkstra’s on negative-weight graphs
This is the most conceptually important mistake. The algorithm will run without crashing but will produce wrong answers silently. Always check for negative weights before choosing your algorithm.
- When asked about shortest paths in an interview, always ask: “Are edge weights non-negative?” If yes, Dijkstra. If no (or unknown), Bellman-Ford.
- Know the O((V+E) log V) complexity and be able to explain why the binary heap gives that bound.
- Be able to trace through the algorithm on a small example — this is the most common follow-up after explaining the concept.
Practice Problems
- Run Dijkstra’s on the graph from this article but with source node B instead of A. What are the shortest distances to all other nodes?
- Add a node G connected to F with weight 3 and to D with weight 1. What is the shortest path from A to G?
- Why does Dijkstra’s run in O(V²) with a simple array but O((V+E) log V) with a binary heap? Walk through the cost of each operation.
- Describe a specific graph where the O(V²) array implementation is faster than the O((V+E) log V) heap version.
- Convert the undirected graph from this article to a directed graph where all edges go left-to-right (A→B, A→C, B→D, etc.). Does Dijkstra’s output change?
Frequently Asked Questions
Does Dijkstra’s work on directed graphs?
Yes. The algorithm works identically on directed graphs — you simply only follow edges in their specified direction when relaxing neighbors. The undirected case is equivalent to a directed graph where every edge exists in both directions.
Can Dijkstra’s find the shortest path between two specific nodes?
Yes. Run the full algorithm from the source node. Stop early when the destination node is extracted from the priority queue — at that point its shortest distance is finalized. Reconstruct the path by following the predecessor table backwards from destination to source.
What happens if two nodes have the same distance in the priority queue?
The algorithm can break ties arbitrarily — the final shortest distances will be correct regardless of which tied node is processed first. Different tie-breaking rules may produce different shortest paths of equal cost, but never a path that isn’t optimal.