Dijkstra's Shortest Path Algorithm

Generated on 2025-07-10 01:56:45 Algorithm Cheatsheet for Technical Interviews

Dijkstra’s Shortest Path Algorithm - Cheatsheet

1. Quick Overview

What is it? Dijkstra’s algorithm finds the shortest path from a starting node to all other nodes in a weighted graph. It works by iteratively exploring the graph, maintaining a set of visited nodes and a priority queue of unvisited nodes.
When to use it?
- Finding the shortest path in a graph with non-negative edge weights.
- Routing problems (e.g., finding the shortest route between two cities).
- Network optimization (e.g., finding the minimum cost path for data transmission).
- GPS navigation.

2. Time & Space Complexity

Metric	Complexity	Explanation
Time Complexity	O(E log V)	Using a priority queue (heap). E is the number of edges and V is the number of vertices. Can be O(V^2) with a simple array implementation for the priority queue.
Space Complexity	O(V)	To store distances from the source to each vertex, the visited set, and the priority queue.

3. Implementation

Python

import heapq

def dijkstra(graph, start):
    """
    Finds the shortest path from a starting node to all other nodes in a graph.

    Args:
        graph (dict): A dictionary representing the graph.  Keys are nodes, and values are lists of (neighbor, weight) tuples.
        start (node): The starting node.

    Returns:
        dict: A dictionary of shortest distances from the start node to all other nodes.  Returns infinity if no path exists.
    """
    distances = {node: float('inf') for node in graph}  # Initialize distances to infinity
    distances[start] = 0  # Distance from start to itself is 0
    priority_queue = [(0, start)]  # (distance, node) - heapq sorts by the first element (distance)

    while priority_queue:
        dist, node = heapq.heappop(priority_queue)  # Get the node with the smallest distance

        if dist > distances[node]: #optimization skip already processed nodes
            continue

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(priority_queue, (new_dist, neighbor))

    return distances

# Example usage
graph = {
    'A': [('B', 5), ('C', 2)],
    'B': [('A', 5), ('D', 1), ('E', 4)],
    'C': [('A', 2), ('E', 6)],
    'D': [('B', 1)],
    'E': [('B', 4), ('C', 6)]
}

start_node = 'A'
shortest_paths = dijkstra(graph, start_node)
print(f"Shortest paths from {start_node}: {shortest_paths}")

Java

import java.util.*;

public class Dijkstra {

    public static Map<String, Integer> dijkstra(Map<String, List<Pair<String, Integer>>> graph, String start) {
        Map<String, Integer> distances = new HashMap<>();
        for (String node : graph.keySet()) {
            distances.put(node, Integer.MAX_VALUE); // Initialize distances to infinity
        }
        distances.put(start, 0); // Distance from start to itself is 0

        PriorityQueue<Pair<Integer, String>> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
        priorityQueue.offer(new Pair<>(0, start)); // (distance, node)

        while (!priorityQueue.isEmpty()) {
            Pair<Integer, String> current = priorityQueue.poll();
            int dist = current.getKey();
            String node = current.getValue();

            if(dist > distances.get(node)){
                continue;
            }

            for (Pair<String, Integer> neighborPair : graph.get(node)) {
                String neighbor = neighborPair.getKey();
                int weight = neighborPair.getValue();

                int newDist = dist + weight;
                if (newDist < distances.get(neighbor)) {
                    distances.put(neighbor, newDist);
                    priorityQueue.offer(new Pair<>(newDist, neighbor));
                }
            }
        }

        return distances;
    }

    public static void main(String[] args) {
        Map<String, List<Pair<String, Integer>>> graph = new HashMap<>();
        graph.put("A", Arrays.asList(new Pair<>("B", 5), new Pair<>("C", 2)));
        graph.put("B", Arrays.asList(new Pair<>("A", 5), new Pair<>("D", 1), new Pair<>("E", 4)));
        graph.put("C", Arrays.asList(new Pair<>("A", 2), new Pair<>("E", 6)));
        graph.put("D", Arrays.asList(new Pair<>("B", 1)));
        graph.put("E", Arrays.asList(new Pair<>("B", 4), new Pair<>("C", 6)));

        String startNode = "A";
        Map<String, Integer> shortestPaths = dijkstra(graph, startNode);
        System.out.println("Shortest paths from " + startNode + ": " + shortestPaths);
    }

    // Helper class for pairs
    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <map>

using namespace std;

map<char, int> dijkstra(const map<char, vector<pair<char, int>>>& graph, char start) {
    map<char, int> distances;
    for (auto const& [node, _] : graph) {
        distances[node] = numeric_limits<int>::max(); // Initialize distances to infinity
    }
    distances[start] = 0; // Distance from start to itself is 0

    priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> priority_queue;
    priority_queue.push({0, start}); // (distance, node)

    while (!priority_queue.empty()) {
        int dist = priority_queue.top().first;
        char node = priority_queue.top().second;
        priority_queue.pop();

        if(dist > distances[node]){
            continue;
        }

        for (const auto& neighbor_pair : graph.at(node)) {
            char neighbor = neighbor_pair.first;
            int weight = neighbor_pair.second;

            int new_dist = dist + weight;
            if (new_dist < distances[neighbor]) {
                distances[neighbor] = new_dist;
                priority_queue.push({new_dist, neighbor});
            }
        }
    }

    return distances;
}

int main() {
    map<char, vector<pair<char, int>>> graph = {
        {'A', {{'B', 5}, {'C', 2}}},
        {'B', {{'A', 5}, {'D', 1}, {'E', 4}}},
        {'C', {{'A', 2}, {'E', 6}}},
        {'D', {{'B', 1}}},
        {'E', {{'B', 4}, {'C', 6}}}
    };

    char start_node = 'A';
    map<char, int> shortest_paths = dijkstra(graph, start_node);

    cout << "Shortest paths from " << start_node << ":" << endl;
    for (auto const& [node, distance] : shortest_paths) {
        cout << node << ": " << distance << endl;
    }

    return 0;
}

4. Common Patterns

Finding the shortest path between two specific nodes: Run Dijkstra’s from the start node until you reach the destination node. You can stop the algorithm early once the destination has been popped off the priority queue.
Graph Representation: The graph can be represented using an adjacency list or an adjacency matrix. Adjacency lists are generally preferred for sparse graphs (graphs with fewer edges), while adjacency matrices are better for dense graphs.
Edge Weights: Dijkstra’s algorithm assumes non-negative edge weights. If negative weights are present, you should use the Bellman-Ford algorithm or the SPFA algorithm (which is often faster than Bellman-Ford but can have worse worst-case performance).
Directed vs. Undirected Graphs: Dijkstra’s algorithm works for both directed and undirected graphs. The graph representation will differ slightly depending on whether the graph is directed or undirected. For undirected graphs, you’ll need to add edges in both directions.

5. Pro Tips

Using a Priority Queue (Heap): A priority queue is crucial for efficient implementation. It allows you to quickly retrieve the node with the smallest distance. Use heapq in Python, PriorityQueue in Java, or priority_queue in C++.
Early Termination: If you only need to find the shortest path to a specific destination node, you can terminate the algorithm as soon as that node is dequeued from the priority queue.
Optimization by skipping already processed nodes: In the while loop, check if dist > distances[node]. If this is true, it means that the current shortest distance to node has already been found and processed, so we can skip processing this node again. This optimization can significantly improve performance.
Handling Disconnected Graphs: If the graph is disconnected, some nodes may not be reachable from the starting node. The distances to these nodes will remain at infinity after the algorithm completes.
Integer Overflow: Be mindful of potential integer overflow issues when calculating distances, especially if the graph has large edge weights or long paths. Use long in Java/C++ or consider using a larger number type in Python if necessary.
Negative Cycles: Dijkstra’s algorithm will not work correctly with negative edge weights and will enter an infinite loop if there is a reachable negative cycle.

6. Practice Problems

LeetCode 743. Network Delay Time: You are given a network of n nodes, labeled from 1 to n. You are given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. Send a signal from node k. Return how long it takes for all nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.
- Link: https://leetcode.com/problems/network-delay-time/
LeetCode 1514. Path with Maximum Probability: You are given an undirected weighted graph of n nodes (0-indexed), and an array of edges where edges[i] = [a, b]. Each edge is associated with a probability of success which is stored in a separate array succProb, where succProb[i] is the probability of the ith edge.

Return the probability of reaching the node endNode starting from the node startNode.
- Link: https://leetcode.com/problems/path-with-maximum-probability/
LeetCode 1631. Path With Minimum Effort: You are a hiker preparing for an upcoming hike. You are given a heights map, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to reach the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells along the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
- Link: https://leetcode.com/problems/path-with-minimum-effort/

7. Templates

C++ Template

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <map>

using namespace std;

map<int, int> dijkstra(const map<int, vector<pair<int, int>>>& graph, int start) {
    map<int, int> distances;
    for (auto const& [node, _] : graph) {
        distances[node] = numeric_limits<int>::max();
    }
    distances[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int dist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (dist > distances[u]) continue; // Optimization

        for (const auto& edge : graph.at(u)) {
            int v = edge.first;
            int weight = edge.second;

            if (distances[v] > distances[u] + weight) {
                distances[v] = distances[u] + weight;
                pq.push({distances[v], v});
            }
        }
    }

    return distances;
}

// Example Usage:
int main() {
    map<int, vector<pair<int, int>>> graph;
    // Populate the graph (example)
    graph[0] = {{1, 4}, {2, 2}};
    graph[1] = {{0, 4}, {2, 5}, {3, 10}};
    graph[2] = {{0, 2}, {1, 5}, {3, 3}};
    graph[3] = {{1, 10}, {2, 3}};

    int startNode = 0;
    map<int, int> shortestPaths = dijkstra(graph, startNode);

    cout << "Shortest paths from node " << startNode << ":" << endl;
    for (auto const& [node, distance] : shortestPaths) {
        cout << "Node " << node << ": " << distance << endl;
    }
    return 0;
}

Python Template

import heapq

def dijkstra(graph, start):
    """
    Finds the shortest path from a starting node to all other nodes in a graph.

    Args:
        graph (dict): A dictionary representing the graph.  Keys are nodes, and values are lists of (neighbor, weight) tuples.
        start (node): The starting node.

    Returns:
        dict: A dictionary of shortest distances from the start node to all other nodes.  Returns infinity if no path exists.
    """
    distances = {node: float('inf') for node in graph}  # Initialize distances to infinity
    distances[start] = 0  # Distance from start to itself is 0
    priority_queue = [(0, start)]  # (distance, node) - heapq sorts by the first element (distance)

    while priority_queue:
        dist, node = heapq.heappop(priority_queue)  # Get the node with the smallest distance

        if dist > distances[node]: #optimization skip already processed nodes
            continue

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(priority_queue, (new_dist, neighbor))

    return distances


# Example usage (replace with your graph)
graph = {
    0: [(1, 4), (2, 2)],
    1: [(0, 4), (2, 5), (3, 10)],
    2: [(0, 2), (1, 5), (3, 3)],
    3: [(1, 10), (2, 3)]
}

start_node = 0
shortest_paths = dijkstra(graph, start_node)
print(f"Shortest paths from {start_node}: {shortest_paths}")

Java Template

import java.util.*;

public class DijkstraTemplate {

    public static Map<Integer, Integer> dijkstra(Map<Integer, List<Pair<Integer, Integer>>> graph, int start) {
        Map<Integer, Integer> distances = new HashMap<>();
        for (Integer node : graph.keySet()) {
            distances.put(node, Integer.MAX_VALUE); // Initialize distances to infinity
        }
        distances.put(start, 0); // Distance from start to itself is 0

        PriorityQueue<Pair<Integer, Integer>> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
        priorityQueue.offer(new Pair<>(0, start)); // (distance, node)

        while (!priorityQueue.isEmpty()) {
            Pair<Integer, Integer> current = priorityQueue.poll();
            int dist = current.getKey();
            int node = current.getValue();

            if(dist > distances.get(node)){
                continue;
            }

            for (Pair<Integer, Integer> neighborPair : graph.get(node)) {
                int neighbor = neighborPair.getKey();
                int weight = neighborPair.getValue();

                int newDist = dist + weight;
                if (newDist < distances.get(neighbor)) {
                    distances.put(neighbor, newDist);
                    priorityQueue.offer(new Pair<>(newDist, neighbor));
                }
            }
        }

        return distances;
    }

    public static void main(String[] args) {
        // Example Graph (replace with your graph)
        Map<Integer, List<Pair<Integer, Integer>>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(new Pair<>(1, 4), new Pair<>(2, 2)));
        graph.put(1, Arrays.asList(new Pair<>(0, 4), new Pair<>(2, 5), new Pair<>(3, 10)));
        graph.put(2, Arrays.asList(new Pair<>(0, 2), new Pair<>(1, 5), new Pair<>(3, 3)));
        graph.put(3, Arrays.asList(new Pair<>(1, 10), new Pair<>(2, 3)));

        int startNode = 0;
        Map<Integer, Integer> shortestPaths = dijkstra(graph, startNode);
        System.out.println("Shortest paths from " + startNode + ": " + shortestPaths);
    }

    // Helper class for pairs
    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}