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) - for distance array, parent array, and 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 for very large graphs (O(E + V log V))

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 between locations
• 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