•
•
•
•
•
•
•
Step-by-step guide with pseudocode, a worked example, time complexity and the 2025 sorting barrier breakthrough
Dijkstra's algorithm is one of the most important shortest path algorithms in computer science, and a staple of coding interviews, network routing and map navigation. This guide explains how Dijkstra's algorithm works step by step, with pseudocode, a worked example, time complexity and the 2025 breakthrough that finally beat its long-standing speed limit.
Dijkstra's algorithm finds the shortest path from one starting node, the source, to every other node in a weighted graph. It is named after Dutch computer scientist Edsger W. Dijkstra and works when every edge weight is zero or positive.
It is a greedy algorithm. At each step it permanently settles the closest unvisited node, because with non-negative weights no route through a farther node can be shorter.
dist[source] = 0; all other dist = infinity
push (0, source) into min-heap
while heap is not empty:
(d, u) = pop smallest
if d > dist[u]: continue
for each edge (u, v, w):
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
push (dist[v], v)Take an undirected graph with these edges: A–B (4), A–C (2), C–B (1), B–D (5), C–D (8) and D–E (3). Find the shortest path from A.
| Step | Node Settled | Distances Updated |
|---|---|---|
| 1 | A (0) | B = 4, C = 2 |
| 2 | C (2) | B = 3, D = 10 |
| 3 | B (3) | D = 8 |
| 4 | D (8) | E = 11 |
| 5 | E (11) | none |
The shortest path from A to E is A → C → B → D → E with a total cost of 11. Notice that the direct A–B edge (4) lost to the route through C (3).
Performance depends on the priority queue. With a binary heap, Dijkstra's algorithm runs in O((V + E) log V). With a Fibonacci heap it improves to O(E + V log V). A simple array-based version takes O(V²), which can still be sensible for dense graphs. Space complexity is O(V) for the distance and predecessor arrays.
Dijkstra's algorithm fails with negative edge weights. Use Bellman-Ford in that case. For a single target, A\ adds a heuristic that steers the search toward the goal. For all-pairs shortest paths, Floyd-Warshall* is the classic choice.
For decades, Dijkstra's algorithm with a Fibonacci heap was treated as a hard speed limit, because it effectively sorts every vertex by distance. This "sorting barrier" had stood since 1984.
In 2025, Duan Ran's research team at Tsinghua University introduced a deterministic algorithm that runs in O(m log^(2/3) n) time on sparse directed graphs with real weights. It avoids fully sorting all vertices and borrows ideas from Bellman-Ford. The paper won the Best Paper Award at STOC 2025. It is mainly a theoretical milestone for now, so Dijkstra's algorithm remains the standard teaching and engineering choice.
Does Dijkstra's algorithm work with negative weights?
No. Negative edges can break the greedy assumption, so use Bellman-Ford.
How is Dijkstra different from BFS?
Breadth-first search finds shortest paths in unweighted graphs. Dijkstra generalises the idea to weighted graphs.
What is the difference between Dijkstra and A\*?
A* uses a heuristic estimate to head toward one target, while Dijkstra explores outward evenly in all directions.
Dijkstra's algorithm remains a cornerstone of search and routing. Master its priority queue logic and relaxation step, and you will understand the foundation behind many modern pathfinding systems.