Dijkstra's Algorithm (and A*)

Dijkstra's algorithm finds the cheapest path when edges have different, non-negative weights. It works like BFS with one change: BFS expands by number of steps, while Dijkstra always expands the path that has cost the least so far. Picture pouring water on a map. It runs quickly along cheap roads and slowly along expensive ones, and Dijkstra computes the moment the water reaches each place.

The idea#

Keep a min-heap of (cost so far, node). Pop the cheapest entry. Because no weight is negative, no path still waiting in the heap can get cheaper by going further, so the first time a node is popped its cost is final. Then push each neighbor with cost + weight.

That leaves one question: what happens when the same node lands in the heap twice? The version here, often called lazy Dijkstra, doesn't update entries inside the heap. It pushes duplicates and ignores the stale ones later:

1. The heap holds both (10, A) and (5, A).
2. (5, A) pops first, and A is finalized at 5.
3. When (10, A) pops later, A is already final, so you throw the entry away.

All of this rests on "first pop is final", and negative weights break that rule. For graphs with negative edges, use Bellman-Ford instead.

How to spot it#

These cues point at Dijkstra:

• "Shortest path" / "minimum cost" / "fastest route" with weighted edges.
• "How long until every node receives the signal?": a question about the shortest distance to all nodes at once.
• "Minimum effort" or "maximum probability" along a path.
• A cost limit on top of the path, such as "at most K stops".

BFS or Dijkstra?#

Some of these questions can look like BFS questions at first. The deciding question is whether every step costs the same.

The "worst weight on the path" row is easy to miss: Dijkstra also solves problems where a path's cost is its maximum edge (Swim in Rising Water) rather than its sum. Those get their own note: Bottleneck / Minimax Paths.

Template#

The template below is the lazy version from above. Its shape depends on how many answers you need:

• Need the answer for one target? Return as soon as you pop the target.
• Need the answer for all nodes? Run until the heap is empty and keep a dist map.

dist = empty map                       # finalized costs only
heap = [(0, src)]
while heap is not empty:
    cost, node = pop the smallest from heap
    if node in dist: skip              # stale: a cheaper copy won
    dist[node] = cost
    if node is the target: return cost # first pop is final
    for each (nei, w) in neighbors of node:
        if nei not in dist:
            push (cost + w, nei) onto heap
return -1 if there was a target, else dist

Return when the target is popped, not when it is pushed. A push only means "here is one way to get there"; a cheaper way may still be sitting in the heap.

Complexity#

The heap is where the cost comes from. Every edge can cause one push, so the heap holds up to $E$ entries and each push or pop costs $O(\log E)$. The total is $O(E \log E)$. Since $E \le V^2$, $\log E \le 2 \log V$, so this is the same as $O(E \log V)$. Space is $O(V + E)$ for the graph, the heap and dist.

A* search (advanced)#

Dijkstra spreads out evenly in every direction, like an expanding circle. When you only need the path to one known target and the search space is large, much of that work is wasted. A* is Dijkstra with a sense of direction: it points a flashlight beam at the goal. Each node gets a priority:

$f(n) = g(n) + h(n)$

Dijkstra asks "which node has been reached most cheaply so far?" A* asks "which node gives the best estimate of the final total cost?". With $h(n) = 0$, A* is exactly Dijkstra.

Admissibility#

Everything A* gains comes from $h$, so a bad estimate can cost you the right answer. A* returns the shortest path only if $h$ is admissible: it must never overestimate the true remaining cost. An optimistic guess only makes A* look at a few extra nodes. A pessimistic one can push the real best path down the heap, so A* reaches the goal along a worse path first and returns it.

On an 8-direction grid where a diagonal step costs 1 (as in LC 1091), each move changes each coordinate by at most 1. So you need at least $\max(|dr|, |dc|)$ moves, which is the Chebyshev distance, and it never overestimates. Euclidean distance does overestimate here: from (0, 0) to (3, 3) the true cost is 3 moves, but the straight-line distance is $3\sqrt{2} \approx 4.24$. Use Euclidean (or octile) distance only when a diagonal step truly costs $\sqrt{2}$.

Which heuristic?#

So how do you pick $h$? On LeetCode you don't invent one. Two standard patterns cover almost everything, and the moves a problem allows tell you which to use.

If the nodes have no coordinates or other structure, there is usually no useful heuristic, so you don't use A*.

A* template#

This is the same loop as Dijkstra, keyed on $f = g + h$ instead of cost alone. It keeps the best known $g$ for each node and uses it to skip stale heap entries.

best_g = {start: start cost}
heap = [(start cost + h(start), start cost, start)]
while heap is not empty:
    f, g, node = pop the smallest from heap
    if node is the goal: return g
    if g > best_g[node]: skip          # stale entry
    for each next reachable from node:
        new_g = g + step cost
        if new_g < best_g.get(next, infinity):
            best_g[next] = new_g
            push (new_g + h(next), new_g, next) onto heap
return -1

With BFS, Dijkstra and A* all covered, here's how to choose between them for any shortest-path question:

1. Unweighted (every step costs 1)? Use BFS; A* is overkill.
2. Weighted graph or grid? Use Dijkstra.
3. Huge search space and a known target position or state? Consider A*.

Pitfalls#

These are the mistakes that most often cost a correct answer.

• Marking a node visited when you push it. A cheaper path found later is then ignored.
• Returning when the target is pushed instead of popped.
• Leaving out the stale-entry skip: a stale, larger cost can overwrite the final one, and nodes get expanded again and again.
• Using Dijkstra with negative weights.
• "All nodes" questions: forgetting the -1 when some node is never reached.
• A*: a heuristic that overestimates, so A* returns a worse path.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Network Delay Time.

• 743. Network Delay Time
• 1514. Path with Maximum Probability
• 1631. Path With Minimum Effort
• 1091. Shortest Path in Binary Matrix
• 787. Cheapest Flights Within K Stops
• 773. Sliding Puzzle
• 675. Cut Off Trees for Golf Event

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Dijkstra = BFS with a min-heap keyed on cost so far; weights must be non-negative.
• The first pop of a node is final, so skip any later (stale) copies.
• One target: return when it is popped. All nodes: keep a dist map.
• $O(E \log E) = O(E \log V)$.
• A* adds an admissible estimate $h$; Chebyshev for unit-cost diagonals, Manhattan for 4 directions, and $h = 0$ gives back Dijkstra.