Dijkstra's algorithm finds the shortest path from a starting vertex to every other vertex in a weighted graph, as long as no edge has a negative weight. It is greedy in the purest sense: at each step it commits to the closest not-yet-finalized vertex, and it never revisits that decision. That single greedy choice, repeated with a priority queue tracking what is closest so far, is the entire algorithm — the elegance is why it has stayed the default shortest-path algorithm since 1956.
What changed in 2026
- The algorithm itself has not changed — it is nearly seventy years old and mathematically settled — but its role in routing, logistics, and network protocols keeps growing as graphs get larger and latency budgets get tighter.
- A (A-star), Dijkstra's heuristic-guided sibling, remains the default upgrade* for pathfinding where a good distance estimate to the goal exists, such as maps or games, cutting down the search space plain Dijkstra's algorithm would otherwise explore.
- Bidirectional and contraction-hierarchy variants dominate production mapping software, running Dijkstra-style search from both ends simultaneously or over a precomputed simplified graph, because plain Dijkstra's algorithm is too slow at continental road-network scale.
How it actually works
Dijkstra(graph, start):
dist[start] = 0
dist[all others] = infinity
pq = min-heap of (distance, vertex), starting with (0, start)
while pq is not empty:
(d, u) = pq.pop_min()
if d > dist[u]: continue # stale entry, skip
for each neighbor v of u with edge weight w:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pq.push((dist[v], v))
return dist
Every time a shorter path to a neighbor is found, that neighbor distance is updated and re-added to the priority queue — this step is called relaxation. The min-heap is what turns grab-the-closest-unvisited-vertex into an O(log n) operation instead of an O(n) scan.
Why it needs non-negative weights
Dijkstra's algorithm finalizes a vertex distance the moment it is popped from the priority queue, assuming no future path could possibly be shorter. A negative edge weight breaks that assumption — a longer-looking path could still turn out cheaper after a negative edge — so the algorithm can produce wrong answers on graphs with negative weights. Bellman-Ford handles negative weights correctly, and detects negative cycles, at the cost of O(V·E) instead of Dijkstra's O((V+E) log V).
Dijkstra vs the alternatives
| Algorithm |
Handles negative weights |
Time complexity |
Best for |
| BFS |
N/A, unweighted only |
O(V + E) |
Unweighted shortest path |
| Dijkstras algorithm |
No |
O((V+E) log V) with a heap |
Weighted, non-negative graphs |
| Bellman-Ford |
Yes |
O(V · E) |
Graphs that may have negative weights |
| A* |
No, needs an admissible heuristic |
Depends on heuristic quality |
Single-target search with a good distance estimate |
Where it actually gets used
- GPS and mapping software — road networks are naturally weighted graphs, distance or travel time, with contraction hierarchies layered on top for speed at scale.
- Network routing protocols such as OSPF use Dijkstra's algorithm directly to compute the shortest path tree across routers.
- Game pathfinding for non-player characters, often upgraded to A* once a reasonable heuristic, such as straight-line distance, is available.
- Any cheapest-way-from-A-to-B problem with non-negative costs — currency arbitrage detection is a notable exception, since it needs Bellman-Ford specifically to find negative cycles.
Common pitfalls
Running it on a graph with negative edges and trusting the result. It terminates and returns an answer, just not necessarily the correct one. Check for negative weights before choosing Dijkstra's algorithm.
Using a plain array scan instead of a min-heap. It still works, but drops from O((V+E) log V) to O(V²), which matters enormously on large graphs.
Confusing it with BFS. BFS finds the shortest path by edge count on an unweighted graph; Dijkstra's algorithm finds the shortest path by total weight. Running plain BFS on a weighted graph gives the wrong answer unless every edge happens to weigh the same.
FAQ
Is Dijkstra's algorithm a greedy algorithm?
Yes — it is one of the canonical examples taught alongside the concept of a greedy algorithm: it always finalizes the closest unvisited vertex and never reconsiders that choice, and that greedy strategy happens to be provably correct here.
Why does Dijkstra's algorithm fail with negative edge weights?
Because it assumes a vertex shortest distance is final once popped from the priority queue. A negative weight later in the graph could still produce a cheaper path, which the algorithm has already ruled out.
What is the time complexity of Dijkstra's algorithm?
O((V + E) log V) using a binary heap-based priority queue, where V is vertices and E is edges. A naive array-based implementation is O(V²), which can actually be faster on very dense graphs.
How is A different from Dijkstra's algorithm?*
A* adds a heuristic estimate of remaining distance to the goal, letting it skip exploring vertices unlikely to be on the shortest path. Dijkstra's algorithm is A* with the heuristic set to zero — it explores uniformly in all directions.
Where to go next