Dijkstra's Algorithm

Intuition

Suppose you are planning drives out of your home city and every road has a travel time. The nearest town to you is easy: no other route can beat driving straight there, because any detour would start with a road at least as long. Once that town is settled, the next-closest town is either a direct neighbor of home or a neighbor of the town you just settled. Dijkstra's algorithm repeats that argument: always settle the unsettled node with the smallest known distance, then use it to improve the estimates of its neighbors.

The argument only works because roads never have negative times. Adding an edge can never make a path shorter, so once the cheapest frontier node is chosen, nothing discovered later can undercut it. A min-heap (priority queue) hands us that cheapest frontier node in O(log n) time instead of scanning every node.

How it works step by step

1. Set dist[src] = 0 and every other distance to infinity. Push (0, src) onto a min-heap ordered by distance.
2. Pop the smallest (d, u) from the heap.
3. If d > dist[u], this entry is stale: a shorter route to u was already found and processed. Skip it. This is lazy deletion.
4. Otherwise u is settled. For each edge u → v with weight w, compute nd = d + w.
5. If nd < dist[v], relax the edge: set dist[v] = nd, record prev[v] = u, and push (nd, v). The old entry for v stays in the heap and will be skipped later.
6. Repeat until the heap is empty. If you only need one target, you can stop the first time it is popped.

Dry run on a weighted directed graph

Edges A→B (4), A→C (1), C→B (2), B→D (1), C→D (5). Source A. The heap column lists entries in priority order after the action.

Following prev from D gives D ← B ← C ← A, so the cheapest route is A → C → B → D with cost 4, even though the direct-looking A → B → D costs 5. The two stale entries in steps 4 and 6 are the price of lazy deletion: cheap to leave behind, cheap to skip.

Code

import java.util.*;

public class Dijkstra {
    // adj.get(u) holds edges as {v, weight}; every weight must be >= 0.
    public static long[] shortestPaths(List<List<int[]>> adj, int src) {
        int n = adj.size();
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(e -> e[0]));
        pq.offer(new long[]{0, src});

        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue;            // stale entry (lazy deletion)
            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                long nd = d + edge[1];
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.offer(new long[]{nd, v});
                }
            }
        }
        return dist;                              // Long.MAX_VALUE = unreachable
    }
}

import heapq


def dijkstra(graph, src):
    """graph maps node -> list of (neighbor, weight). Returns (dist, prev)."""
    dist = {node: float("inf") for node in graph}
    prev = {src: None}
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # stale entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, prev


def path_to(prev, target):
    if target not in prev:
        return []
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return path[::-1]


graph = {"A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": []}
dist, prev = dijkstra(graph, "A")
print(dist)                  # {'A': 0, 'B': 3, 'C': 1, 'D': 4}
print(path_to(prev, "D"))    # ['A', 'C', 'B', 'D']

Time and space complexity

With lazy deletion the heap can hold up to E entries, so each operation costs O(log E). Because E is at most V squared, log E is at most 2 log V, which is why the bound is still written as O((V + E) log V).

Edge cases

• Unreachable nodes keep distance infinity; convert to -1 only at the end if the problem asks for it.
• Zero-weight edges are fine. Only negative weights break correctness.
• Parallel edges between the same pair are handled naturally; only the cheapest one wins a relaxation.
• Overflow: in Java, adding to Integer.MAX_VALUE wraps negative. Use long distances or check for infinity before adding.
• Undirected graphs: add every edge in both directions when building the adjacency list.

Why negative edges break Dijkstra

Take edges A→B (2), A→C (3), C→B (-2). Dijkstra pops A, then pops B at distance 2 and declares it settled. Later it pops C at 3 and discovers A → C → B costs 1, but B was already finalised, and anything computed from B's old value is now wrong. The greedy guarantee assumed no future edge could lower a settled distance, and a negative weight does exactly that. Bellman-Ford fixes this by relaxing every edge V - 1 times in O(V x E), and a further pass that still improves something proves a negative cycle exists. **A* search** goes the other direction: it keeps Dijkstra's non-negative assumption but adds a heuristic estimate of the remaining distance to the target, so on maps and grids it settles far fewer nodes. Explore it in the A* search lesson.

Common mistakes

• Forgetting the if d > dist[u]: continue check. The result is still correct, but stale entries re-relax neighbors and blow up the running time.
• Marking a node as visited when it is pushed instead of when it is popped. Unlike BFS, a node's first discovery is not necessarily its cheapest.
• Pushing (node, dist) instead of (dist, node) into Python's heapq, which then orders by node id.
• Using Dijkstra on a graph where all weights are 1. Plain BFS gives the same answer without the log factor.
• Assuming it handles extra constraints like at most K stops. Those need the constraint inside the state, or Bellman-Ford limited to K rounds.

Variations and when to use it

Use Dijkstra for single-source cheapest paths with non-negative costs: network latency, travel time, grid movement where cells have different costs. The same loop solves minimax problems such as path with minimum effort by replacing d + w with max(d, w), and maximum probability paths by using a max-heap and multiplying. When the graph is unweighted, prefer Graph BFS. When edge weights are only 0 or 1, the 0-1 BFS deque is linear time.

Related LeetCode problems

• #743 Network Delay Time — run Dijkstra from the source and return the largest finite distance.
• #1514 Path with Maximum Probability — max-heap version where relaxing means multiplying probabilities.
• #1631 Path With Minimum Effort — grid Dijkstra where a path's cost is its largest single step.
• #778 Swim in Rising Water — minimax Dijkstra on a grid of elevations.
• #1976 Number of Ways to Arrive at Destination — Dijkstra that also counts how many shortest paths reach each node.
• #787 Cheapest Flights Within K Stops — shows the limit of plain Dijkstra; add stops to the state or use bounded Bellman-Ford.
• #1368 Minimum Cost to Make at Least One Valid Path in a Grid — 0-1 weights, solvable with Dijkstra or a deque.

FAQ