Dijkstra's Algorithm

Dijkstra's algorithm is a fundamental graph algorithm that finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a greedy approach with a priority queue to efficiently compute optimal paths.

Interactive Visualization

Start Node

End Node

Speed (ms)

800ms

Node States

Unvisited

Start Node

End Node

Current

Visited

Shortest Path

Drag nodes to reposition • Click to reset • 5 nodes, 7 edges

Dijkstra's Algorithm

Algorithm Overview:

Dijkstra's algorithm finds the shortest path between nodes in a weighted graph. It works by maintaining a set of unvisited nodes and continuously selecting the node with the smallest distance.

Time Complexity: O((V + E) log V) with priority queue

Space Complexity: O(V)

Key Features:

Guarantees shortest path in weighted graphs
Uses a greedy approach with priority queue
Works with non-negative edge weights
Optimal for single-source shortest path problems

Greedy Shortest Path Strategy

Dijkstra's algorithm employs a greedy strategy that always selects the unvisited vertex with the minimum distance from the source. This locally optimal choice leads to a globally optimal solution for finding shortest paths in graphs with non-negative edge weights.

1. Initialize

Set distance to source as 0, all others as infinity; use priority queue

2. Extract Minimum

Remove vertex with minimum distance from priority queue

3. Relax Edges

Update distances to neighbors if shorter path is found

Key Insight

The greedy choice works because once a vertex is processed (removed from the priority queue), we have found the shortest path to it. This is guaranteed by the non-negative weight constraint - any future path through other vertices cannot be shorter.

How Dijkstra's Algorithm Works

Step-by-Step Process

Initialize: Set distance[source] = 0, distance[all others] = ∞

Priority Queue: Add source vertex to priority queue with distance 0

Extract Min: Remove vertex with minimum distance from queue

Relax Edges: For each neighbor, update distance if shorter path found

Repeat: Continue until all vertices processed or queue is empty

Edge Relaxation Process

Current Distance: distance[u] (shortest known distance to current vertex u)

Edge Weight: weight(u, v) (weight of edge from u to neighbor v)

New Distance: distance[u] + weight(u, v)

Update Condition: If new distance < distance[v], update distance[v]

Priority Queue: Add/update v in priority queue with new distance

Example: Finding Shortest Paths from A

Graph: A-B(4), A-D(2), B-C(3), B-E(1), C-F(1), D-E(5), E-F(3)

Initial: dist[A]=0, dist[others]=∞, queue=[(0,A)]

Step 1: Process A, update dist[B]=4, dist[D]=2

Step 2: Process D (min=2), update dist[E]=7

Step 3: Process B (min=4), update dist[C]=7, dist[E]=5

Step 4: Process E (min=5), update dist[F]=8

Final: A:0, B:4, C:7, D:2, E:5, F:8

Pseudocode

ALGORITHM Dijkstra(graph, source)
BEGIN
    // Initialize distances and priority queue
    FOR each vertex v IN graph DO
        distance[v] = INFINITY
        previous[v] = UNDEFINED
    END FOR
    
    distance[source] = 0
    priorityQueue = empty priority queue
    visited = empty set
    
    // Add source to priority queue
    priorityQueue.insert(source, 0)
    
    // Main algorithm loop
    WHILE priorityQueue is not empty DO
        // Extract vertex with minimum distance
        u = priorityQueue.extractMin()
        
        // Skip if already processed
        IF u IN visited THEN
            CONTINUE
        END IF
        
        // Mark as visited
        visited.add(u)
        
        // Process all neighbors of u
        FOR each neighbor v OF u DO
            IF v IN visited THEN
                CONTINUE
            END IF
            
            // Calculate new distance through u
            newDistance = distance[u] + weight(u, v)
            
            // Relax edge if shorter path found
            IF newDistance < distance[v] THEN
                distance[v] = newDistance
                previous[v] = u
                priorityQueue.insert(v, newDistance)
            END IF
        END FOR
    END WHILE
    
    RETURN distance, previous
END

// Reconstruct shortest path from source to target
ALGORITHM GetPath(previous, source, target)
BEGIN
    path = empty list
    current = target
    
    WHILE current is not UNDEFINED DO
        path.prepend(current)
        current = previous[current]
    END WHILE
    
    IF path[0] != source THEN
        RETURN empty list  // No path exists
    END IF
    
    RETURN path
END

Complexity Analysis

Implementation	Time Complexity	Space Complexity	Explanation
Binary Heap	O((V + E) log V)	O(V)	Standard implementation with priority queue
Fibonacci Heap	O(E + V log V)	O(V)	Theoretical optimum with amortized analysis
Simple Array	O(V²)	O(V)	Linear search for minimum distance vertex

Why O((V + E) log V)?

• Vertex Processing: Each vertex is extracted from priority queue once: O(V log V)
• Edge Relaxation: Each edge is relaxed at most once: O(E log V)
• Priority Queue Operations: Insert/decrease-key in O(log V) time
• Total Operations: O(V log V + E log V) = O((V + E) log V)

Space Complexity Breakdown

• Distance Array: O(V) space to store shortest distances
• Previous Array: O(V) space for path reconstruction
• Priority Queue: O(V) space for unprocessed vertices
• Visited Set: O(V) space to track processed vertices

Critical Requirement: Non-negative Weights

Dijkstra's algorithm only works with non-negative edge weights. Negative weights violate the greedy property and can lead to incorrect results.

Why Negative Weights Fail:
• Greedy choice becomes invalid
• Already processed vertices might need updates
• Algorithm terminates with wrong distances

Alternative for Negative Weights:
• Bellman-Ford algorithm
• Floyd-Warshall for all-pairs
• Johnson's algorithm for sparse graphs

Code Examples

Here are implementations of Dijkstra's algorithm in different programming languages. Each version uses a priority queue for efficiency and includes both single-source shortest paths and point-to-point pathfinding with early termination.

 import heapq
from collections import defaultdict

class Graph:
    def __init__(self):
        self.vertices = defaultdict(list)
    
    def add_edge(self, from_vertex, to_vertex, weight):
        """Add weighted edge to the graph"""
        self.vertices[from_vertex].append((to_vertex, weight))
    
    def dijkstra(self, start, num_vertices):
        """
        Find shortest paths from start vertex to all other vertices
        Time Complexity: O((V + E) log V)
        Space Complexity: O(V)
        """
        # Initialize distances to infinity
        distances = [float('inf')] * num_vertices
        distances[start] = 0
        
        # Track previous vertices for path reconstruction
        previous = [-1] * num_vertices
        
        # Priority queue: (distance, vertex)
        pq = [(0, start)]
        visited = set()
        
        while pq:
            current_distance, current_vertex = heapq.heappop(pq)
            
            # Skip if already processed
            if current_vertex in visited:
                continue
            
            visited.add(current_vertex)
            
            # Process all neighbors
            for neighbor, weight in self.vertices[current_vertex]:
                if neighbor in visited:
                    continue
                
                # Calculate new distance through current vertex
                new_distance = current_distance + weight
                
                # If we found a shorter path, update it
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    previous[neighbor] = current_vertex
                    heapq.heappush(pq, (new_distance, neighbor))
        
        return distances, previous
    
    def dijkstra_with_target(self, start, target, num_vertices):
        """Find shortest path between two specific vertices"""
        distances = [float('inf')] * num_vertices
        distances[start] = 0
        
        previous = [-1] * num_vertices
        pq = [(0, start)]
        visited = set()
        
        while pq:
            current_distance, current_vertex = heapq.heappop(pq)
            
            if current_vertex in visited:
                continue
            
            visited.add(current_vertex)
            
            # Early termination if we reached the target
            if current_vertex == target:
                break
            
            for neighbor, weight in self.vertices[current_vertex]:
                if neighbor in visited:
                    continue
                
                new_distance = current_distance + weight
                
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    previous[neighbor] = current_vertex
                    heapq.heappush(pq, (new_distance, neighbor))
        
        # Reconstruct path
        path = []
        current = target
        
        while current != -1:
            path.append(current)
            current = previous[current]
        
        path.reverse()
        
        # Check if path is valid
        if not path or path[0] != start:
            path = []  # No path exists
        
        return distances[target], path

# Example usage
if __name__ == "__main__":
    # Create graph: A=0, B=1, C=2, D=3, E=4, F=5
    graph = Graph()
    num_vertices = 6
    
    # Add edges (bidirectional)
    edges = [
        (0, 1, 4), (0, 3, 2),  # A-B, A-D
        (1, 0, 4), (1, 2, 3), (1, 4, 1),  # B-A, B-C, B-E
        (2, 1, 3), (2, 4, 2), (2, 5, 1),  # C-B, C-E, C-F
        (3, 0, 2), (3, 4, 5),  # D-A, D-E
        (4, 1, 1), (4, 2, 2), (4, 3, 5), (4, 5, 3),  # E-B, E-C, E-D, E-F
        (5, 2, 1), (5, 4, 3)   # F-C, F-E
    ]
    
    for from_v, to_v, weight in edges:
        graph.add_edge(from_v, to_v, weight)
    
    start = 0  # Node A
    distances, previous = graph.dijkstra(start, num_vertices)
    
    print(f"Shortest distances from vertex {start}:")
    node_names = ['A', 'B', 'C', 'D', 'E', 'F']
    
    for i in range(num_vertices):
        distance = "∞" if distances[i] == float('inf') else distances[i]
        print(f"  To {node_names[i]}: {distance}")
    
    # Find shortest path to specific vertex
    target = 5  # Node F
    distance, path = graph.dijkstra_with_target(start, target, num_vertices)
    
    print(f"\nShortest path from {node_names[start]} to {node_names[target]}:")
    path_names = [node_names[node] for node in path]
    print(f"  Path: {' -> '.join(path_names)}")
    print(f"  Distance: {distance}") 
 import java.util.*;

class Edge {
    int target;
    int weight;
    
    public Edge(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }
}

class Node implements Comparable<Node> {
    int id;
    int distance;
    
    public Node(int id, int distance) {
        this.id = id;
        this.distance = distance;
    }
    
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.distance, other.distance);
    }
}

public class DijkstraAlgorithm {
    private List<List<Edge>> graph;
    private int numVertices;
    
    public DijkstraAlgorithm(int numVertices) {
        this.numVertices = numVertices;
        this.graph = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            graph.add(new ArrayList<>());
        }
    }
    
    public void addEdge(int from, int to, int weight) {
        graph.get(from).add(new Edge(to, weight));
    }
    
    /**
     * Find shortest paths from start vertex to all other vertices
     */
    public int[] dijkstra(int start) {
        int[] distances = new int[numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;
        
        int[] previous = new int[numVertices];
        Arrays.fill(previous, -1);
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        
        boolean[] visited = new boolean[numVertices];
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentVertex = current.id;
            
            if (visited[currentVertex]) {
                continue;
            }
            
            visited[currentVertex] = true;
            
            for (Edge edge : graph.get(currentVertex)) {
                int neighbor = edge.target;
                int weight = edge.weight;
                
                if (visited[neighbor]) {
                    continue;
                }
                
                int newDistance = distances[currentVertex] + weight;
                
                if (newDistance < distances[neighbor]) {
                    distances[neighbor] = newDistance;
                    previous[neighbor] = currentVertex;
                    pq.offer(new Node(neighbor, newDistance));
                }
            }
        }
        
        return distances;
    }
    
    /**
     * Find shortest path between two specific vertices
     */
    public PathResult dijkstraWithTarget(int start, int target) {
        int[] distances = new int[numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;
        
        int[] previous = new int[numVertices];
        Arrays.fill(previous, -1);
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        
        boolean[] visited = new boolean[numVertices];
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentVertex = current.id;
            
            if (visited[currentVertex]) {
                continue;
            }
            
            visited[currentVertex] = true;
            
            // Early termination if we reached the target
            if (currentVertex == target) {
                break;
            }
            
            for (Edge edge : graph.get(currentVertex)) {
                int neighbor = edge.target;
                int weight = edge.weight;
                
                if (visited[neighbor]) {
                    continue;
                }
                
                int newDistance = distances[currentVertex] + weight;
                
                if (newDistance < distances[neighbor]) {
                    distances[neighbor] = newDistance;
                    previous[neighbor] = currentVertex;
                    pq.offer(new Node(neighbor, newDistance));
                }
            }
        }
        
        // Reconstruct path
        List<Integer> path = new ArrayList<>();
        int current = target;
        
        while (current != -1) {
            path.add(current);
            current = previous[current];
        }
        
        Collections.reverse(path);
        
        // Check if path is valid
        if (path.isEmpty() || path.get(0) != start) {
            path.clear(); // No path exists
        }
        
        return new PathResult(distances[target], path);
    }
    
    public static void main(String[] args) {
        // Create graph: A=0, B=1, C=2, D=3, E=4, F=5
        int numVertices = 6;
        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(numVertices);
        
        // Add edges (bidirectional)
        dijkstra.addEdge(0, 1, 4); dijkstra.addEdge(0, 3, 2); // A-B, A-D
        dijkstra.addEdge(1, 0, 4); dijkstra.addEdge(1, 2, 3); dijkstra.addEdge(1, 4, 1); // B-A, B-C, B-E
        dijkstra.addEdge(2, 1, 3); dijkstra.addEdge(2, 4, 2); dijkstra.addEdge(2, 5, 1); // C-B, C-E, C-F
        dijkstra.addEdge(3, 0, 2); dijkstra.addEdge(3, 4, 5); // D-A, D-E
        dijkstra.addEdge(4, 1, 1); dijkstra.addEdge(4, 2, 2); dijkstra.addEdge(4, 3, 5); dijkstra.addEdge(4, 5, 3); // E connections
        dijkstra.addEdge(5, 2, 1); dijkstra.addEdge(5, 4, 3); // F-C, F-E
        
        int start = 0; // Node A
        int[] distances = dijkstra.dijkstra(start);
        
        System.out.println("Shortest distances from vertex " + start + ":");
        char[] nodeNames = {'A', 'B', 'C', 'D', 'E', 'F'};
        
        for (int i = 0; i < numVertices; i++) {
            String distance = distances[i] == Integer.MAX_VALUE ? "∞" : String.valueOf(distances[i]);
            System.out.println("  To " + nodeNames[i] + ": " + distance);
        }
        
        // Find shortest path to specific vertex
        int target = 5; // Node F
        PathResult result = dijkstra.dijkstraWithTarget(start, target);
        
        System.out.println("\nShortest path from " + nodeNames[start] + " to " + nodeNames[target] + ":");
        for (int node : result.path) {
            System.out.print(nodeNames[node] + " ");
        }
        System.out.println("\nDistance: " + result.distance);
    }
}

class PathResult {
    int distance;
    List<Integer> path;
    
    public PathResult(int distance, List<Integer> path) {
        this.distance = distance;
        this.path = path;
    }
} 
 #include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <iostream>
using namespace std;

// Edge structure to represent weighted edges
struct Edge {
    int target;
    int weight;
    
    Edge(int t, int w) : target(t), weight(w) {}
};

// Node structure for priority queue
struct Node {
    int id;
    int distance;
    
    Node(int i, int d) : id(i), distance(d) {}
    
    // For min-heap (priority queue with smallest distance first)
    bool operator>(const Node& other) const {
        return distance > other.distance;
    }
};

/**
 * Find shortest paths from start node to all other nodes using Dijkstra's algorithm.
 * 
 * @param graph Adjacency list representation of the graph
 * @param start Starting node (0-indexed)
 * @param numNodes Total number of nodes in the graph
 * @return Vector of shortest distances from start to all nodes
 * 
 * Time Complexity: O((V + E) log V) with binary heap
 * Space Complexity: O(V)
 * Requirement: All edge weights must be non-negative
 */
vector<int> dijkstra(const vector<vector<Edge>>& graph, int start, int numNodes) {
    // Initialize distances to infinity
    vector<int> distances(numNodes, INT_MAX);
    distances[start] = 0;
    
    // Track previous nodes for path reconstruction
    vector<int> previous(numNodes, -1);
    
    // Priority queue for selecting minimum distance node
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push(Node(start, 0));
    
    vector<bool> visited(numNodes, false);
    
    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        
        int currentNode = current.id;
        
        // Skip if already processed
        if (visited[currentNode]) {
            continue;
        }
        
        visited[currentNode] = true;
        
        // Process all neighbors
        for (const Edge& edge : graph[currentNode]) {
            int neighbor = edge.target;
            int weight = edge.weight;
            
            if (visited[neighbor]) {
                continue;
            }
            
            // Calculate new distance through current node
            int newDistance = distances[currentNode] + weight;
            
            // If we found a shorter path, update it
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
                previous[neighbor] = currentNode;
                pq.push(Node(neighbor, newDistance));
            }
        }
    }
    
    return distances;
}

/**
 * Find shortest path between two specific nodes.
 */
pair<int, vector<int>> dijkstraWithTarget(const vector<vector<Edge>>& graph, 
                                         int start, int target, int numNodes) {
    vector<int> distances(numNodes, INT_MAX);
    distances[start] = 0;
    
    vector<int> previous(numNodes, -1);
    
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push(Node(start, 0));
    
    vector<bool> visited(numNodes, false);
    
    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        
        int currentNode = current.id;
        
        if (visited[currentNode]) {
            continue;
        }
        
        visited[currentNode] = true;
        
        // Early termination if we reached the target
        if (currentNode == target) {
            break;
        }
        
        for (const Edge& edge : graph[currentNode]) {
            int neighbor = edge.target;
            int weight = edge.weight;
            
            if (visited[neighbor]) {
                continue;
            }
            
            int newDistance = distances[currentNode] + weight;
            
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
                previous[neighbor] = currentNode;
                pq.push(Node(neighbor, newDistance));
            }
        }
    }
    
    // Reconstruct path
    vector<int> path;
    int current = target;
    
    while (current != -1) {
        path.push_back(current);
        current = previous[current];
    }
    
    reverse(path.begin(), path.end());
    
    // Check if path is valid
    if (path.empty() || path[0] != start) {
        path.clear(); // No path exists
    }
    
    return make_pair(distances[target], path);
}

int main() {
    // Create graph: A=0, B=1, C=2, D=3, E=4, F=5
    int numNodes = 6;
    vector<vector<Edge>> graph(numNodes);
    
    // Add edges (bidirectional)
    graph[0].push_back(Edge(1, 4)); // A-B
    graph[0].push_back(Edge(3, 2)); // A-D
    graph[1].push_back(Edge(0, 4)); // B-A
    graph[1].push_back(Edge(2, 3)); // B-C
    graph[1].push_back(Edge(4, 1)); // B-E
    graph[2].push_back(Edge(1, 3)); // C-B
    graph[2].push_back(Edge(4, 2)); // C-E
    graph[2].push_back(Edge(5, 1)); // C-F
    graph[3].push_back(Edge(0, 2)); // D-A
    graph[3].push_back(Edge(4, 5)); // D-E
    graph[4].push_back(Edge(1, 1)); // E-B
    graph[4].push_back(Edge(2, 2)); // E-C
    graph[4].push_back(Edge(3, 5)); // E-D
    graph[4].push_back(Edge(5, 3)); // E-F
    graph[5].push_back(Edge(2, 1)); // F-C
    graph[5].push_back(Edge(4, 3)); // F-E
    
    int start = 0; // Node A
    vector<int> distances = dijkstra(graph, start, numNodes);
    
    cout << "Shortest distances from node " << start << ":" << endl;
    vector<char> nodeNames = {'A', 'B', 'C', 'D', 'E', 'F'};
    
    for (int i = 0; i < numNodes; i++) {
        cout << "  To " << nodeNames[i] << ": ";
        if (distances[i] == INT_MAX) {
            cout << "∞";
        } else {
            cout << distances[i];
        }
        cout << endl;
    }
    
    // Find shortest path to specific node
    int target = 5; // Node F
    auto result = dijkstraWithTarget(graph, start, target, numNodes);
    
    cout << "\nShortest path from " << nodeNames[start] << " to " << nodeNames[target] << ": ";
    for (int node : result.second) {
        cout << nodeNames[node] << " ";
    }
    cout << "\nDistance: " << result.first << endl;
    
    return 0;
} 

Practical Applications

Perfect For

• GPS Navigation: Finding shortest routes in road networks
• Network Routing: Optimal packet routing in computer networks
• Social Networks: Finding shortest connection paths between users
• Flight Planning: Shortest travel times between airports
• Game Pathfinding: AI navigation with weighted terrain costs
• Resource Allocation: Minimum cost flow problems

Consider Alternatives When

• Negative Weights: Use Bellman-Ford or Johnson's algorithm
• All-Pairs Shortest Paths: Floyd-Warshall may be more suitable
• Unweighted Graphs: Simple BFS is faster and simpler
• Very Dense Graphs: Consider O(V²) implementation
• Dynamic Graphs: Frequent edge updates make preprocessing costly

Real-World Applications

Transportation Systems: Google Maps, Uber route optimization, public transit planning, delivery logistics, airline scheduling, traffic management systems, emergency services routing

Network Systems: Internet routing protocols (OSPF), telecommunications switching, network topology optimization, bandwidth allocation, distributed systems communication, peer-to-peer networks