Dijkstra's Algorithm

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

Video Explanation​

Watch

Interactive Visualization​

Below is an interactive visualizer for Dijkstra's algorithm. You can click Start Dijkstra to watch the algorithm explore nodes and update distances using a min-priority queue, or click Next Step to step through the execution manually!

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​

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.