Dijkstra's Algorithm

Overview

Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a weighted graph with non-negative edge weights. It finds the shortest path from a source vertex to all other vertices in the graph.

The algorithm works by maintaining a set of vertices whose shortest distances from the source are known, and iteratively selecting the vertex with the minimum distance that hasn't been processed yet. It uses a greedy approach, always choosing the closest unvisited vertex, which guarantees optimality for graphs with non-negative weights.

Dijkstra's algorithm is widely used in routing protocols, GPS navigation systems, network routing, and any application where finding the shortest path in a weighted graph is required.

Dijkstra's algorithm is probably the single most useful graph algorithm in day-to-day computing. It is what your car's navigation system uses to compute the route to a destination, what OSPF-based network routers use to build their forwarding tables, what game engines use for pathfinding, what social networks use to compute "shortest connection" paths between users. The only algorithm that comes close in ubiquity is BFS, and BFS is essentially the special case of Dijkstra's when every edge has weight 1.

History: A Twenty-Minute Algorithm

Edsger Dijkstra designed the algorithm in about twenty minutes while shopping in Amsterdam with his fiancée Ria in 1956. This is not apocryphal. Dijkstra tells the story himself in his 2001 paper "An interview with Edsger W. Dijkstra": they were at a café on the terrace of the Rijksmuseum, waiting for a tram, and Dijkstra was thinking about how to find the shortest route between two cities in the Netherlands for a demonstration of the ARMAC computer his employer was about to unveil. He worked out the algorithm in his head, without paper or pencil, in the twenty minutes it took to drink his coffee. He published it three years later, in 1959, in the first volume of the journal Numerische Mathematik as a two-and-a-half-page paper titled "A Note on Two Problems in Connexion with Graphs."

Dijkstra's paper actually presented two algorithms: what we now call Dijkstra's shortest-path algorithm, and Prim's minimum spanning tree algorithm (which had also been independently discovered by Robert C. Prim and Vojtěch Jarník earlier). The two algorithms are structurally very similar, both greedily grow a frontier by repeatedly extracting the minimum edge weight, and Dijkstra treated them together as instances of a more general pattern.

A historical footnote: the algorithm's original motivation was display, not routing. Dijkstra wanted to demonstrate that a computer could solve a problem that people could relate to. Finding the shortest route between two Dutch cities was picked because a room full of Dutch engineers could look at the answer and see whether it looked plausible. The routing applications that now dominate the algorithm's use came later; the entire ARPANET routing protocol infrastructure that made the internet possible was still a decade away.

Why It Requires Non-Negative Weights

Dijkstra's greedy correctness argument depends on a specific claim that fails when edge weights can be negative:

Claim: when we extract a vertex v from the priority queue with distance d, then d is the true shortest-path distance from the source to v.

Proof sketch: at the moment we extract v, its current dist[v] = d was set by relaxing some edge (u, v) where u was already extracted with its true shortest distance. Any other path to v must go through some vertex w still in the queue, but every such w has dist[w] ≥ d (otherwise we would have extracted w before v), and any path from w to v adds non-negative weight, so any alternate path to v has weight ≥ d. Therefore d is optimal.

Why negative weights break this. The argument that "any path from w to v adds non-negative weight" fails if edges can be negative, an alternate path via w might traverse a negative-weight edge that reduces its total below d, even though w's own distance is higher than d. So we cannot conclude that v's distance is final when we extract it. Real inputs where this bites: currency conversion (where log of exchange rate can be negative), edge-cost changes in dynamic settings (relative time differences), some formulations of shortest paths in signed graphs. For any of these, use Bellman-Ford instead.

A common misconception: people sometimes propose "just add a large constant to every edge weight to make them non-negative, then run Dijkstra's, then subtract." This does not work, adding a constant changes the shortest path, because a path with more edges accumulates more constants than a path with fewer edges. The correct reweighting technique is Johnson's algorithm, which uses Bellman-Ford to compute vertex potentials that transform edge weights while preserving shortest paths.

Modern Improvements and the 2025 Result

Dijkstra's algorithm has been the standard for single-source shortest paths for 65 years, and for most of that time its O((V + E) log V) complexity was thought to be close to optimal for the general case. In practice, several classes of improvements change this picture.

Fibonacci heaps, invented by Fredman and Tarjan in 1984, give Dijkstra's an amortised O(V log V + E) bound, strictly better on dense graphs. The constant factors are so large that Fibonacci heaps almost never beat binary heaps in practice, but they are the theoretically best known complexity for Dijkstra's using pairwise comparisons.

Contraction hierarchies and hub labelling, developed in the 2000s at Karlsruhe Institute of Technology and elsewhere, are preprocessing-based techniques that dramatically speed up repeated shortest-path queries on the same graph. Real GPS navigation systems use these to answer coast-to-coast queries in a few milliseconds against continent-sized road networks, something plain Dijkstra's could not do quickly enough for interactive use. A one-time preprocessing pass builds an augmented representation of the graph, and subsequent queries run bidirectional search over that representation.

The 2025 breakthrough. Duan, Mao, Mao, Shu and Yin's paper at STOC 2025 broke the "sorting barrier" for directed single-source shortest paths, the algorithm runs in O(m log^2/3 n) deterministic time, the first improvement on Dijkstra's O(m + n log n) in decades. The technique combines ideas from bucketing, priority queue design, and careful management of the frontier. It is theoretically important but has not yet been implemented in a way that is faster than Dijkstra's on real-world inputs; the constants are large. The result is a reminder that even 65-year-old algorithms can be improved when the right idea comes along.

Practical Implementation Choices

Priority Queue Choice

The complexity of Dijkstra's depends critically on the priority queue implementation.

• Binary heap (Python's heapq): O((V + E) log V). This is the default choice and the one shown in the code above. Excellent for sparse graphs.
• Array-based priority queue: O(V²). Better than binary heap when the graph is very dense (E ≈ V²). Rarely used in practice because most real graphs are sparse.
• Fibonacci heap: O(E + V log V) amortised. Theoretically better, practically slower than a binary heap because of constant factors.
• Bucket-based priority queue (Dial's algorithm): O(V + E + wV) where w is the maximum edge weight. Beats a heap when the weights are small bounded integers. Used in some routing implementations where all edge weights are in a known small range.

Lazy Deletion vs. Decrease-Key

Python's heapq does not support the decrease-key operation. The implementation shown above uses lazy deletion: when we find a better distance to a vertex, we push a new (distance, vertex) tuple onto the heap without removing the old one, and skip stale entries when we pop them. This is simpler than implementing decrease-key and works well in practice, at the cost of the heap potentially holding O(E) entries rather than O(V).

The alternative, using an indexed priority queue that supports decrease-key, is a strict improvement in worst case but adds significant code complexity. For most real applications the lazy version is fine and is what production libraries like NetworkX and scipy's shortest_path use internally.

Early Termination for Single-Target Queries

If you only need the shortest path from source to a specific target (not to all vertices), stop the algorithm as soon as you extract the target from the queue. Its distance is guaranteed correct at that point, and continuing to process further vertices is wasted work. This can be a huge speedup on large graphs where the target is close to the source.

Bidirectional Search

For single-source, single-target queries, run Dijkstra's from both endpoints simultaneously and stop when the two frontiers meet. This explores roughly O(V^0.5) times fewer vertices in favourable cases, a real win on continent-sized road networks. The implementation is fiddly because of the "when do the frontiers really meet with the shortest path" condition, but it is a standard component of every production routing engine.

How It Works

The algorithm follows these steps:

1. Initialize: Set distance to source as 0, and all other distances as infinity
2. Priority Queue: Add all vertices to a priority queue (min-heap) based on distance
3. Iterate: While the queue is not empty:
   • Extract the vertex with minimum distance
   • Mark it as processed
   • For each neighbor, relax edges if a shorter path is found
   • Update distances and parent pointers
4. Result: Distances array contains shortest distances from source to all vertices

Dijkstra's Algorithm Pseudocode

Dijkstra(graph, source):
    dist[source] = 0
    dist[v] = ∞ for all other vertices v
    parent[v] = null for all vertices
    visited = set()
    priority_queue = min_heap containing all vertices
    
    while priority_queue is not empty:
        u = extract_min(priority_queue)
        visited.add(u)
        
        for each neighbor v of u:
            if v not in visited:
                new_dist = dist[u] + weight(u, v)
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    parent[v] = u
                    decrease_key(priority_queue, v, new_dist)
    
    return dist, parent
                

Implementation

import heapq

def dijkstra(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    parent = [-1] * n
    visited = [False] * n
    
    # Priority queue: (distance, vertex)
    pq = [(0, start)]
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        if visited[u]:
            continue
        
        visited[u] = True
        
        for v, weight in graph[u]:
            if not visited[v]:
                new_dist = current_dist + weight
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    parent[v] = u
                    heapq.heappush(pq, (new_dist, v))
    
    return dist, parent

def reconstruct_path(parent, target):
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = parent[current]
    return path[::-1]
                

Complexity Analysis

• Time Complexity:
  • With binary heap: O((V + E) log V)
  • With Fibonacci heap: O(E + V log V)
  • With array (dense graphs): O(V²)
• Space Complexity: O(V + E) for the implementation below. The distance and parent arrays are O(V), but this version uses lazy deletion, it pushes a new heap entry on every successful relaxation rather than decreasing an existing key, so the heap can hold up to O(E) entries. A decrease_key-based implementation keeps the heap at O(V), at the cost of needing an indexed priority queue.

The time complexity depends on the data structure used for the priority queue. For sparse graphs, a binary heap is efficient. For dense graphs, an array-based approach might be faster.

Requirements and Limitations

• Non-negative weights: Dijkstra's algorithm requires all edge weights to be non-negative. It fails with negative weights.
• Connected graph: Works on both connected and disconnected graphs (unreachable vertices remain at infinity).
• Directed/Undirected: Works on both directed and undirected graphs.
• Single source: Finds shortest paths from one source vertex to all others.

For graphs with negative edge weights, use the Bellman-Ford algorithm instead.

Example

Finding shortest paths from vertex 0:

Graph:
    0 --3--> 1
    |        |
    1        4
    |        |
    v        v
    2 --2--> 3

Step 1: Start at 0, dist[0] = 0
Step 2: Process 0, update neighbors 1 and 2
        dist[1] = 3, dist[2] = 1
Step 3: Process 2 (minimum), update neighbor 3
        dist[3] = 3
Step 4: Process 1, update neighbor 3
        dist[3] = min(3, 3+4) = 3 (no change)
Step 5: Process 3 (done)

Result: dist = [0, 3, 1, 3]
Shortest path from 0 to 3: 0 → 2 → 3 (distance 3)
                

Optimizations

• Early Termination: Stop when target vertex is processed (for single-target queries)
• Bidirectional Search: Run Dijkstra from both source and target simultaneously
• A* Algorithm: Use heuristic function to guide search (extension of Dijkstra)
• Fibonacci Heap: better asymptotics (O(E + V log V)), but the constant factors are large enough that binary heaps usually win in practice

Beyond Dijkstra's

Dijkstra's O(m + n log n) was long assumed to be the best possible for directed graphs with real weights, the "sorting barrier", since the algorithm effectively sorts vertices by distance. In 2025 that assumption was overturned: Duan, Mao, Mao, Shu and Yin gave a deterministic O(m log^2/3 n) algorithm for directed single-source shortest paths, winning the STOC 2025 best paper award. It works by combining Dijkstra-style relaxation with Bellman-Ford-style rounds to avoid fully sorting the frontier. It is a theoretical result rather than something you would implement, but it settles a question that stood for over sixty years.

For undirected graphs with integer weights, Thorup (1999) gave a genuinely linear O(m) algorithm.

When to Use Dijkstra's Algorithm

Dijkstra's algorithm is ideal when:

• You need shortest paths in a weighted graph with non-negative edges
• Finding paths from one source to all other vertices
• Graph is sparse (few edges relative to vertices)
• Real-time pathfinding in games or navigation systems
• Network routing protocols

Consider alternatives when:

• Graph has negative weights → Use Bellman-Ford
• Unweighted graph → Use BFS (simpler, O(V + E))
• All-pairs shortest paths → Use Floyd-Warshall

Dijkstra vs Other Shortest Path Algorithms

Real-World Applications

• GPS Navigation: finding shortest routes. Note that production routing engines do not run plain Dijkstra's on a continental road network, that would take seconds per query. They precompute: contraction hierarchies, hub labeling, or ALT (A* with landmarks) answer queries in microseconds after an offline preprocessing step.
• Network Routing: Routing packets in computer networks
• Social Networks: Finding shortest connection paths
• Game Development: Pathfinding for AI characters
• Traffic Management: Optimizing traffic flow
• Telecommunications: Routing phone calls efficiently

Related Algorithms

Explore other graph algorithms:

• Breadth-First Search (BFS) - Shortest path for unweighted graphs
• Depth-First Search (DFS) - Graph traversal
• Union-Find - Connected components
• Back to Graph Algorithms Overview