Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph.

Important Limitation

Dijkstra's algorithm is greedy and assumes all edge weights are non-negative. If a graph has negative edge weights, Dijkstra's algorithm might fail. Use the Bellman-Ford Algorithm instead in such cases.

---

How It Works

The algorithm uses a Min-Priority Queue to continually select the unvisited vertex with the smallest known distance from the source.

Steps

1. Initialize the distance to the source node as 0, and all other nodes to ∞.
2. Insert all nodes into a priority queue based on their current distances.
3. While the priority queue is not empty:
   • Extract the node u with the minimum distance.
   • For each neighbor v of u:
     • Calculate the new distance dist[u] + weight(u, v).
     • If this new distance is less than the current dist[v], update dist[v] and update the priority queue.

---

Complexity Analysis

Metric	Value
Time Complexity	O((V + E) log V)
Space Complexity	O(V)

Where V = number of vertices, E = number of edges. The time complexity assumes the use of a Priority Queue / Min-Heap.

---

Implementations

Python

import heapq

def dijkstra(graph, start):
    # Initialize distances
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # Priority queue stores (distance, node)
    pq = [(0, start)]
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        # Optimization: ignore obsolete entries in the priority queue
        if current_distance > distances[current_node]:
            continue
            
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
                
    return distances

Java

import java.util.*;

public class Dijkstra {
    static class Node implements Comparable<Node> {
        int vertex, weight;
        Node(int v, int w) { vertex = v; weight = w; }
        public int compareTo(Node other) { return Integer.compare(this.weight, other.weight); }
    }

    public static int[] dijkstra(int V, List<List<Node>> graph, int source) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(source, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.vertex;

            if (current.weight > dist[u]) continue;

            for (Node neighbor : graph.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.weight;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        return dist;
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

vector<int> dijkstra(int V, vector<vector<pii>>& graph, int source) {
    vector<int> dist(V, 1e9); // 1e9 represents infinity
    dist[source] = 0;
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, source});
    
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

JavaScript

class PriorityQueue {
    constructor() { this.values = []; }
    enqueue(val, priority) {
        this.values.push({val, priority});
    }
    dequeue() {
        let minIdx = 0;
        for (let i = 1; i < this.values.length; i++) {
            if (this.values[i].priority < this.values[minIdx].priority) {
                minIdx = i;
            }
        }
        return this.values.splice(minIdx, 1)[0];
    }
    isEmpty() { return this.values.length === 0; }
}

function dijkstra(graph, start) {
    const distances = {};
    const pq = new PriorityQueue();
    
    for (let node in graph) {
        distances[node] = Infinity;
    }
    distances[start] = 0;
    pq.enqueue(start, 0);
    
    while (!pq.isEmpty()) {
        const {val: current_node, priority: current_distance} = pq.dequeue();
        
        if (current_distance > distances[current_node]) continue;
        
        for (let neighbor in graph[current_node]) {
            let distance = current_distance + graph[current_node][neighbor];
            
            if (distance < distances[neighbor]) {
                distances[neighbor] = distance;
                pq.enqueue(neighbor, distance);
            }
        }
    }
    return distances;
}

---

Real-World Use Cases

• Google Maps — Routing and finding the fastest path between cities or locations.
• Network Routing Protocols — OSPF (Open Shortest Path First) uses Dijkstra's algorithm to compute the shortest path for data packets.
• Video Games — Pathfinding algorithms for NPCs to navigate maps while avoiding obstacles.