Dijkstra's Shortest Path

Finding the Cheapest Route

Imagine you are booking a flight from New York to San Francisco. There are dozens of possible routes through intermediate cities, each leg with a different price. You want the cheapest total fare. This is the single-source shortest path problem on a weighted graph: given a starting node and non-negative edge weights, find the minimum-cost path to every other node.

Breadth-first search cannot solve this. BFS explores nodes layer by layer, where each layer represents one more edge traversed. It finds the path with the fewest edges, not the path with the lowest total weight. A direct flight costing $800 has fewer edges than a two-hop route costing$200 + $150 =$350, but BFS would prefer the direct flight. When edges have different weights, we need an algorithm that accounts for cost, not just hop count.

Dijkstra's algorithm is that algorithm. Published by Edsger Dijkstra in 1959, it efficiently computes shortest paths from a single source to all other nodes in a graph with non-negative edge weights.

The Greedy Insight

Dijkstra's algorithm is built on a greedy observation: if you always process the unvisited node with the smallest known distance, you can be certain that its distance is final.

Why? Suppose node u has the smallest tentative distance among all unvisited nodes. Could there be a cheaper path to u that goes through some other unvisited node v? That path would have to reach v first, but v's tentative distance is already greater than or equal to u's. Since all edge weights are non-negative, continuing from v to u can only add more cost. So no undiscovered path to u can beat the current one. The distance to u is settled.

This greedy guarantee is the heart of Dijkstra's algorithm. It means we can process nodes in order of their distance from the source, and each node only needs to be processed once.

Min-Heap Implementation

We implement this greedy selection using a min-heap (priority queue). The heap stores pairs of (distance, node), and we always pop the pair with the smallest distance.

The algorithm proceeds as follows. Initialize a distance array with infinity for every node, except the source which gets distance 0. Push (0, source) onto the heap. Then repeatedly pop the smallest entry. If the popped distance is larger than the current best distance for that node, skip it, because this entry is stale. Otherwise, examine each neighbor: if routing through the current node offers a shorter path, update the neighbor's distance and push the new pair onto the heap.

The Stale Entry Check

The "skip if stale" check deserves special attention because it is essential to correctness and performance. When we find a shorter path to a node, we push a new entry onto the heap, but the old entry with the larger distance is still sitting in there. We do not remove it (removing from the middle of a heap is expensive). Instead, when we eventually pop that old entry, we compare its distance to the current best. If the popped distance is greater than what we have recorded, we know this entry is outdated and skip it.

Without this check, we would re-process nodes multiple times with suboptimal distances, potentially relaxing their neighbors again unnecessarily. In the worst case, this can degrade performance significantly and produce incorrect intermediate results.

Walking Through a Small Graph

Consider a graph with 5 nodes (0 through 4) and these edges with weights:

0 to 1 with weight 4, 0 to 2 with weight 1, 2 to 1 with weight 2, 1 to 3 with weight 1, 2 to 3 with weight 5, 3 to 4 with weight 3.

We want shortest paths from node 0.

Start: dist = [0, inf, inf, inf, inf]. Heap: [(0, 0)].

Pop (0, 0). Process neighbors: node 1 gets dist 4, node 2 gets dist 1. dist = [0, 4, 1, inf, inf]. Heap: [(1, 2), (4, 1)].

Pop (1, 2). Distance 1 matches dist[2], so process it. Neighbors: node 1 currently has dist 4, but through node 2 the cost is 1 + 2 = 3, which is better. Update dist[1] = 3. Node 3 gets dist 1 + 5 = 6. dist = [0, 3, 1, 6, inf]. Heap: [(3, 1), (4, 1), (6, 3)].

Pop (3, 1). Distance 3 matches dist[1], so process it. Neighbor: node 3 currently has dist 6, but through node 1 the cost is 3 + 1 = 4, which is better. Update dist[3] = 4. dist = [0, 3, 1, 4, inf]. Heap: [(4, 1), (4, 3), (6, 3)].

Pop (4, 1). Distance 4 is greater than dist[1] = 3. This is a stale entry, so skip it.

Pop (4, 3). Distance 4 matches dist[3], so process it. Neighbor: node 4 gets dist 4 + 3 = 7. dist = [0, 3, 1, 4, 7]. Heap: [(6, 3)].

Pop (6, 3). Distance 6 is greater than dist[3] = 4. Stale, so skip it.

Heap is empty. Final distances from node 0: [0, 3, 1, 4, 7]. The shortest path to node 1 goes through node 2 (cost 1 + 2 = 3), not the direct edge (cost 4). The shortest path to node 4 is 0 -> 2 -> 1 -> 3 -> 4 with total cost 7.

Code: Dijkstra's Algorithm

import heapq

def dijkstra(graph, n, source):
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # stale entry, skip
        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dist

The graph is represented as an adjacency list where graph[u] contains pairs (v, w) meaning there is an edge from u to v with weight w. The function returns the distance array where dist[i] is the shortest distance from the source to node i.

Why Negative Edges Break Dijkstra

Dijkstra's correctness depends entirely on the guarantee that once a node is popped from the heap, its distance is final. Negative edge weights destroy this guarantee.

Consider a simple example: nodes A, B, C with edges A to B with weight 1, A to C with weight 3, and C to B with weight -5. Dijkstra pops A first (distance 0), then processes neighbors: B gets distance 1, C gets distance 3. Next it pops B (distance 1) and considers B settled. But the path A -> C -> B has cost 3 + (-5) = -2, which is cheaper. By the time we process C, it is too late: B has already been finalized with distance 1.

The fundamental issue is that with negative edges, a longer path (in terms of intermediate cost) can become shorter after traversing a negative edge. The greedy assumption that "closer nodes are settled" no longer holds. For graphs with negative edges, you need Bellman-Ford, which relaxes all edges repeatedly and can detect negative cycles.

Application: Network Delay Time

LeetCode 743 gives you n nodes representing servers and a list of directed edges with travel times. You send a signal from a source node and need to find the time it takes for all nodes to receive the signal. This is the maximum of all shortest paths from the source.

Run Dijkstra from the source node. The answer is the maximum value in the distance array. If any node remains at infinity, it is unreachable, and you return -1.

def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))

    dist = [float('inf')] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]

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

    result = max(dist[1:])
    return result if result < float('inf') else -1

Application: Path with Minimum Effort

LeetCode 1631 presents a grid of heights where you need to find a path from the top-left to the bottom-right that minimizes the maximum absolute height difference along any single step. This is not a standard shortest path in the additive sense, but Dijkstra adapts naturally.

Think of it as a graph where each cell is a node, and the edge weight between adjacent cells is the absolute difference in their heights. But instead of summing weights along a path, you take the maximum. The "distance" to a cell is the minimum possible effort (maximum single-step difference) over all paths to that cell.

Dijkstra works here because the max operation, like addition, is monotonically non-decreasing when edge weights are non-negative. If the current effort to reach u is e, then going to a neighbor v will result in effort max(e, |height[u] - height[v]|), which is always at least e. So the greedy property holds: when we pop a cell from the heap, its effort is final.

def minimumEffortPath(heights):
    rows, cols = len(heights), len(heights[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    dist[0][0] = 0
    heap = [(0, 0, 0)]  # (effort, row, col)

    while heap:
        effort, r, c = heapq.heappop(heap)
        if r == rows - 1 and c == cols - 1:
            return effort  # early termination
        if effort > dist[r][c]:
            continue
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                new_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
                if new_effort < dist[nr][nc]:
                    dist[nr][nc] = new_effort
                    heapq.heappush(heap, (new_effort, nr, nc))

    return dist[rows-1][cols-1]

Application: Path with Maximum Probability

Path with Maximum Probability (LC 1514) gives you an undirected graph where each edge has a success probability between 0 and 1. You want the path from start to end that maximizes the product of edge probabilities.

Standard Dijkstra minimizes a sum, but here we maximize a product. The adaptation is straightforward: use a max-heap instead of a min-heap, and multiply instead of add. The greedy property still holds: since all probabilities are in [0, 1], extending a path can only keep or reduce its probability, so the highest-probability entry in the heap is finalized when popped.

import heapq

def maxProbability(n, edges, succProb, start, end):
    graph = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, succProb[i]))
        graph[v].append((u, succProb[i]))

    dist = [0.0] * n
    dist[start] = 1.0
    heap = [(-1.0, start)]  # negate for max-heap

    while heap:
        neg_prob, u = heapq.heappop(heap)
        prob = -neg_prob
        if u == end:
            return prob
        if prob < dist[u]:
            continue  # stale entry
        for v, w in graph[u]:
            new_prob = prob * w
            if new_prob > dist[v]:
                dist[v] = new_prob
                heapq.heappush(heap, (-new_prob, v))

    return 0.0

The key differences from standard Dijkstra: probabilities are negated for the min-heap to simulate a max-heap, the initial "distance" to the source is 1.0 (multiplicative identity), and we multiply edge weights instead of adding them.

Application: Swim in Rising Water

Swim in Rising Water (LC 778) places you on an n x n grid where each cell has an elevation. At time t you can swim through any cell with elevation at most t. Starting at the top-left, find the minimum time to reach the bottom-right.

This is a minimax path problem: you want to minimize the maximum elevation encountered along the path. It is structurally identical to Path with Minimum Effort, except the "weight" at each step is the destination cell's elevation rather than an absolute difference.

Modified Dijkstra works naturally: the "distance" to a cell is the minimum possible maximum elevation over all paths reaching it. When moving to a neighbor, the new cost is max(current_cost, elevation[neighbor]). The greedy property holds because max is monotonically non-decreasing with non-negative values.

import heapq

def swimInWater(grid):
    n = len(grid)
    dist = [[float('inf')] * n for _ in range(n)]
    dist[0][0] = grid[0][0]
    heap = [(grid[0][0], 0, 0)]

    while heap:
        t, r, c = heapq.heappop(heap)
        if r == n - 1 and c == n - 1:
            return t
        if t > dist[r][c]:
            continue
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n:
                new_t = max(t, grid[nr][nc])
                if new_t < dist[nr][nc]:
                    dist[nr][nc] = new_t
                    heapq.heappush(heap, (new_t, nr, nc))

    return dist[n-1][n-1]

An alternative approach is binary search on the answer t combined with BFS/DFS to check reachability using only cells with elevation at most t. Both run in $O(n^2 \log n)$ time, but the Dijkstra version is more direct.

Early Termination

When you only need the shortest path to a specific target (not to all nodes), you can return immediately when the target node is popped from the heap. At that moment, its distance is finalized. There is no need to continue processing remaining nodes.

The Path with Minimum Effort code above demonstrates this: it returns as soon as the bottom-right corner is popped. This optimization can save significant work when the target is close to the source relative to the rest of the graph.

Complexity Analysis

With a binary heap, Dijkstra's algorithm runs in $O((V + E) \log V)$ time. Each node is popped from the heap at most once (stale entries are skipped in $O(1)$). Each edge is examined once when its source node is processed, potentially causing a heap push. Each push and pop operation takes $O(log V)$ time since the heap contains at most $O(V)$ non-stale entries at any point (though in practice, with stale entries, the heap can hold up to $O(E)$ entries, making the bound $O((V + E) \log E)$, which simplifies to $O((V + E) \log V)$ since $\log E$ is at most $2 \log V$ for simple graphs).

Space complexity is $O(V + E)$ for the adjacency list and distance array, plus $O(E)$ for the heap in the worst case.

For dense graphs where E approaches $V^2$, Dijkstra with a Fibonacci heap achieves $O(V \log V + E)$, but in practice the binary heap version is fast enough for interview problems and most applications.

Recognizing this pattern

You're probably looking at Dijkstra when:

• You need the shortest path on a weighted graph and all edge weights are non-negative
• The problem talks about minimum cost, minimum time, or cheapest route through nodes with positive weights
• A grid asks for the minimum effort, minimum risk, or minimum cumulative cost between two cells
• BFS is not enough because edges have varying costs, but you don't need to handle negative weights

Common templates:

• Binary-heap Dijkstra on adjacency list: pop the closest unsettled node, relax its outgoing edges. Example: Network Delay Time.
• Grid Dijkstra with custom cost: treat each cell as a node and apply Dijkstra on the implicit graph. Example: Path With Minimum Effort.
• Cheapest path under multiplicative cost: relax using probability multiplication instead of addition, max-heap on success probability. Example: Path with Maximum Probability.
• Modified relaxation for resource constraints: track an extra dimension like fuel or time when relaxing. Example: The Maze II.