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.

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