Dijkstra's Algorithm

The Intuition

Dijkstra's algorithm computes single-source shortest paths in a weighted graph with non-negative edge weights. It generalizes BFS: instead of a FIFO queue that processes nodes in order of hop count, Dijkstra uses a min-heap that processes nodes in order of total distance from the source.

The greedy choice: at every step, finalize the unfinalized node with the smallest tentative distance. The correctness invariant is that any other path to that node must pass through a different unfinalized node, which by definition has a larger tentative distance, and adding non-negative edges only makes paths longer. So the first time a node is popped from the heap, the recorded distance is the true shortest. This is why negative edges break Dijkstra: an unfinalized node could become reachable via a shorter path through a yet-to-be-explored negative edge, violating the invariant.

The heap can contain stale entries: a node may have been pushed several times with different tentative distances as shorter paths were discovered. The standard handling is "lazy deletion": when popping (d, u), if d > dist[u], the entry is stale, skip it. This avoids the cost of an indexed priority queue while keeping the asymptotics at O((V + E) log V).

Three common variants in interviews:

Single-target. Stop the loop the moment the target node is popped, since its distance is now final.
Path reconstruction. Maintain a prev[v] pointer for the predecessor on the shortest path; trace back from target to source after the run.
0-1 BFS. When edge weights are only 0 or 1, replace the heap with a deque: push 0-edges to the front, 1-edges to the back. Total O(V + E). Used for problems like LC 2290 (minimum obstacles to remove).

When to use

Shortest path in weighted graphs with non-negative weights, network routing, navigation systems, or any problem asking for minimum cost paths.

When NOT to use

Negative edge weights (use Bellman-Ford)
Unweighted graph (BFS is simpler and sufficient)
Need all-pairs shortest path (use Floyd-Warshall)

Pattern Recognition

Problem asks for shortest path in a weighted graphProblem involves finding minimum cost to reach a destinationProblem describes network delay or signal propagation time

Edge Cases

Single node graph (distance is zero)
Target node is unreachable from the source
Graph contains zero-weight edges
Graph has negative weights (Dijkstra produces incorrect results)

Practice Problems

MediumNetwork Delay Time

MediumPath with Minimum Effort

MediumCheapest Flights Within K Stops

HardSwim in Rising Water

Key Points

•Finds shortest path from source to all vertices in weighted graphs
•Uses a min-heap (priority queue) to always process the nearest unvisited node
•Does NOT work with negative edge weights. Use Bellman-Ford instead
•Lazy deletion: skip nodes already finalized when popped from heap
•Can reconstruct path by tracking predecessors

Code Template

import heapq

def dijkstra(graph, start, n):
    """Shortest paths from start. graph[u] = [(v, weight), ...]"""
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # stale entry

        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dist

def dijkstra_with_path(graph, start, end, n):
    """Shortest path with reconstruction."""
    dist = [float('inf')] * n
    dist[start] = 0
    prev = [-1] * n
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        if u == end:
            break
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(heap, (new_dist, v))

    # Reconstruct path
    path = []
    node = end
    while node != -1:
        path.append(node)
        node = prev[node]
    return path[::-1] if dist[end] != float('inf') else []

import "container/heap"

type Edge struct{ to, weight int }
type Item struct{ node, dist int }
type MinHeap []Item
func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool   { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)        { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{})  { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} {
    old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x
}

func dijkstra(graph [][]Edge, start, n int) []int {
    // Shortest paths from start.
    dist := make([]int, n)
    for i := range dist { dist[i] = math.MaxInt64 }
    dist[start] = 0

    h := &MinHeap{{start, 0}}
    heap.Init(h)

    for h.Len() > 0 {
        cur := heap.Pop(h).(Item)
        if cur.dist > dist[cur.node] { continue }

        for _, e := range graph[cur.node] {
            newDist := dist[cur.node] + e.weight
            if newDist < dist[e.to] {
                dist[e.to] = newDist
                heap.Push(h, Item{e.to, newDist})
            }
        }
    }
    return dist
}

public int[] dijkstra(List<int[]>[] graph,
                       int start, int n) {
    // Shortest paths from start. graph[u] = [[v, w], ...]
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    // Min-heap: [distance, node]
    PriorityQueue<int[]> heap = new PriorityQueue<>(
        Comparator.comparingInt(a -> a[0]));
    heap.offer(new int[]{0, start});

    while (!heap.isEmpty()) {
        int[] cur = heap.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue; // stale entry

        for (int[] edge : graph[u]) {
            int v = edge[0], w = edge[1];
            int newDist = dist[u] + w;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                heap.offer(new int[]{newDist, v});
            }
        }
    }
    return dist;
}

Common Mistakes

Using with negative edge weights (incorrect results)
Not using lazy deletion (processing stale entries from the heap)
Forgetting to initialize distances to infinity

Related Patterns

CrackingWalnuts

GraphsTemplate 7 of 10

GraphIntermediateO((V + E) log V) time, O(V) space