Shortest Paths: Dijkstra and Bellman-Ford

1The mental model (what this really is)#

One idea runs through both algorithms. Get it and the rest is bookkeeping.

The shared goal.

• Find the cheapest way from a start point to everywhere else (or to one target).
• "Cheap" means the sum of edge weights along a path.
• Picture cities joined by roads, each road a toll, start in one city, find the minimum total toll to reach each other city.
• That is single-source shortest path. Both Dijkstra and Bellman-Ford solve exactly this. They differ in how, and in which graphs they tolerate.

The one operation underneath both: relaxation.

• Keep a best-known distance to every node, starting at infinity for all except the source, which is 0.
• Look at an edge (u, v) with weight w and ask: is going to u then crossing to v cheaper than the current best for v?
• If yes, update v. Done in the right order enough times, this produces the answer.

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

The two tools, side by side.

• Dijkstra: greedy. Always expand the closest unfinalized node next. Once a node leaves the heap, its distance is locked forever. Fast. Breaks the instant a negative edge appears.
• Bellman-Ford: brute force. Relax every edge, repeat V-1 times. Slower by up to a factor of V, but it handles negative weights and detects negative cycles, which Dijkstra cannot do at all.

2How to recognize it (the signals in a problem)#

The problem rarely says "shortest path." It hides. Here is what I train people to listen for.

Phrasings that mean weighted shortest path:

• "Minimum cost / time / effort to get from A to B" across a network of connections with per-step costs.
• "Cheapest flight," "shortest travel time," "minimum cost to reach," with numbers on the edges.
• A grid where each cell has a cost or weight and you move between neighbors. A weighted grid is just Dijkstra on an implicit graph where you never build the adjacency list.
• "Best possible rate / highest probability / least weakness" (maximize, not minimize). Same engine, flipped comparison.
• Negative values, debts, refunds, discounts, or losses on edges. Now you are in Bellman-Ford territory, and currency-arbitrage phrasing is the tell for negative cycles.

The fastest triage, in order:

1. All weights equal (or 1)? Plain BFS already gives shortest path, O(V + E), no heap. Do not bring a heap to a BFS fight.
2. All weights non-negative? Reach for Dijkstra.
3. Any weight negative, or a hop limit? Bellman-Ford (or its queue-based cousin, SPFA).

3The template (how it works, with pseudocode)#

Two templates, memorized cold. Write them from muscle memory and spend your thinking time on the problem, not the plumbing.

Dijkstra with a min-heap. I can write this shape in about 90 seconds, and so should you.

def dijkstra(graph, source, n):
    dist = [infinity] * n
    dist[source] = 0
    heap = [(0, source)]          # (distance, node)

    while heap:
        d, u = pop_min(heap)
        if d > dist[u]:           # stale entry, skip it
            continue
        for (v, w) in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                push(heap, (d + w, v))
    return dist

Two lines earn their keep.

• The if d > dist[u]: continue guard lets you skip decrease-key entirely.
• Instead of fighting the heap to update an existing entry, push a duplicate (new_dist, v) and skip the old one when it surfaces.
• The heap can grow to O(E) entries this way, which is fine, and every interviewer I know accepts it.
• It is cleaner than any decrease-key you will write under pressure.

Bellman-Ford. No heap, just loops over the edge list.

def bellman_ford(edges, source, n):
    dist = [infinity] * n
    dist[source] = 0

    for i in range(n - 1):        # V-1 passes
        changed = False
        for (u, v, w) in edges:
            if dist[u] != infinity and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                 # early exit, nothing left to improve

    # one more pass to detect a negative cycle
    for (u, v, w) in edges:
        if dist[u] != infinity and dist[u] + w < dist[v]:
            return None           # negative cycle reachable from source
    return dist

The details that keep it correct.

• The dist[u] != infinity check matters: without it, infinity + w can wrap or falsely relax an unreached node, and you get phantom paths. Add it and move on.
• Why V-1 passes? The longest simple shortest path touches at most V nodes, so it has at most V-1 edges.
• Each full pass locks in one more edge of that path, in order. After V-1 passes, every shortest path is settled.
• If a V-th pass still improves something, a negative cycle exists, because only an endless loop of discounts could keep lowering the cost below any floor.

4A worked example (walk through one problem step by step)#

Let me run Dijkstra on a tiny graph so you see the greedy order in motion. Nodes A, B, C, D. Edges (directed, with weights):

• A -> B (4)
• A -> C (1)
• C -> B (2)
• B -> D (1)
• C -> D (5)

Source is A. I want the shortest distance to every node.

Start: dist = {A:0, B:inf, C:inf, D:inf}. Heap: [(0, A)].

Pop (0, A). It is fresh. Relax A's edges.

• A -> B: 0 + 4 = 4 < inf. Set dist[B] = 4, push (4, B).
• A -> C: 0 + 1 = 1 < inf. Set dist[C] = 1, push (1, C).

Heap now: [(1, C), (4, B)].

Pop (1, C). This is the greedy heart of it. C is the closest unfinalized node, so Dijkstra commits to dist[C] = 1 as final. Nothing will ever beat it, because every other route to C would have to pass through a node already at distance greater than 1. Relax C's edges.

• C -> B: 1 + 2 = 3 < 4. Better path to B through C. Set dist[B] = 3, push (3, B).
• C -> D: 1 + 5 = 6 < inf. Set dist[D] = 6, push (6, D).

Heap: [(3, B), (4, B), (6, D)]. Notice there are two entries for B now. That stale (4, B) is harmless. We will skip it later, and this is exactly why we push duplicates instead of doing decrease-key.

Pop (3, B). Matches dist[B] = 3, fresh. Relax.

• B -> D: 3 + 1 = 4 < 6. Better. Set dist[D] = 4, push (4, D).

Heap: [(4, B), (4, D), (6, D)].

Pop (4, B). But dist[B] is already 3, and 4 > 3. Stale. Skip. This is exactly what that guard line protects against. Without it, we would reprocess B's edges for nothing.

Pop (4, D). Matches dist[D] = 4, fresh. D has no outgoing edges. Nothing to relax.

Pop (6, D). Stale (6 > 4). Skip. Heap empty. Done.

What the trace proves:

• Final: A:0, C:1, B:3, D:4.
• The shortest path to D is A -> C -> B -> D, total 4, even though it takes three hops.
• The direct-looking A -> B (4) plus B -> D (1) gives 5, which is worse.
• Shortest path means least weight, not fewest edges. That trips people up constantly, and it is the exact confusion that makes people reach for BFS when they should not.

5Variations and gotchas#

The interviewer rarely hands you textbook Dijkstra. Here are the costumes it wears.

• Dijkstra on a grid. No explicit adjacency list. The graph is implicit: neighbors are the up/down/left/right cells (sometimes 8-directional). Generate edges on the fly inside the loop. Same algorithm, same heap, just bounds-check the coordinates.
• Modified objective. "Path with the minimum maximum edge" (minimize the single largest weight you cross) or "path maximizing the minimum" (widest path). Keep Dijkstra's structure but change the relaxation: instead of d + w, use max(d, w) or min(d, w). The heap just sorts by the new cost. This shows up far more than people expect, and it is the whole trick behind Swim in Rising Water and Path With Minimum Effort.
• Probabilities / multiplication. "Maximum probability path." Weights are in 0 to 1 and they multiply instead of add, and you maximize instead of minimize. Use a max-heap and multiply along edges. It is Dijkstra wearing a costume; the greedy proof still holds because multiplying by a value at most 1 never increases probability.
• At most K stops / steps. The cheapest-flights-within-K-stops problem. Plain Dijkstra can return a wrong answer here, because the cheapest path by weight might use too many hops, and Dijkstra finalizes a node before it knows how many hops you will be allowed. Use Bellman-Ford limited to K+1 passes, or a BFS by layers carrying (node, stops). The rule: if there is a hop constraint, lean Bellman-Ford.
• SPFA. A queue-based Bellman-Ford that only reprocesses a node when its distance actually changed. Much faster on typical inputs, same worst case. Worth naming if negatives appear and you want speed, but be honest that its worst case is still O(VE) and adversarial graphs can hit it.
• 0-1 BFS. If every weight is 0 or 1, skip the heap. Use a deque: push 0-weight moves to the front, 1-weight moves to the back. O(V + E), no log factor. Saying this out loud signals real depth, and it is the intended solution to Minimum Obstacle Removal and Minimum Cost to Make at Least One Valid Path.

6Complexity#

Where the bounds come from:

• The log V factor in Dijkstra comes from heap operations, and we may push up to O(E) entries, which is where the E in that bound comes from.
• For dense graphs where E approaches V squared, a simple array-based Dijkstra that scans for the minimum each round runs in O(V squared) and actually beats the heap version, since O(V squared + E) with E near V squared is just O(V squared) while the heap version pays an extra log V.
• Nice to know, rarely needed in interviews, but a clean answer if an interviewer presses on dense graphs.

7Mistakes that cost people the round#

• Reaching for Dijkstra with negative edges. Instant red flag to the interviewer, and they often plant a single negative weight on purpose to see if you check. Always ask or confirm the weight constraint before you commit to an algorithm.
• Forgetting the stale-entry guard. Without if d > dist[u]: continue, you reprocess finalized nodes, inflate your runtime, and sometimes it still returns the right answer, which is worse, because it hides the bug until a harder test case.
• Confusing fewest edges with least weight. BFS gives fewest edges. If weights vary, BFS is simply wrong, even though it compiles and returns a number that looks plausible.
• Using plain Dijkstra on "at most K stops." The classic trap. The hop limit changes the problem, and plenty of people lose the offer right here by finalizing a node too early.
• Not handling unreachable nodes. Some targets stay at infinity. Decide what to return for those (usually -1) and say it out loud. Interviewers watch for this edge case specifically.
• Marking a node visited when you push it, instead of when you pop it. You finalize a node only when it leaves the heap. Marking it visited on push can lock in a non-minimal distance, because a cheaper route might still be sitting deeper in the heap.
• Skipping negative-cycle detection when the problem clearly hints at one. If they mention arbitrage, currency loops, refunds that compound, or "can the cost decrease forever," they want that V-th pass and a None or false return.

Pick the algorithm from the weight constraint, not from reflex.

8Your practice path (named problems by difficulty)#

Do them in this order. Each one teaches a specific muscle, and I have noted which.

Warm up (recognize the pattern):

• Network Delay Time (textbook single-source Dijkstra, build confidence)
• Path With Minimum Effort (Dijkstra with max relaxation on a grid)

Core (the real interview zone):

• Cheapest Flights Within K Stops (the hop-limit trap, Bellman-Ford with K+1 passes shines)
• Path with Maximum Probability (flipped objective, max-heap, multiply along edges)
• Swim in Rising Water (minimize the maximum, grid Dijkstra)
• The Maze II (weighted implicit graph, distance rolls until it hits a wall)

Stretch (level up):

• Minimum Cost to Make at Least One Valid Path in a Grid (0-1 BFS)
• Find the City With the Smallest Number of Neighbors at a Threshold Distance (all-pairs, meet Floyd-Warshall at O(V cubed))
• Reachable Nodes In Subdivided Graph (Dijkstra with a twist on counting subdivided edge nodes)
• Minimum Obstacle Removal to Reach Corner (another 0-1 BFS in disguise)

If you can look at each of these and name the right tool in under 30 seconds, you are interview-ready. That recognition speed is the actual skill being tested, not your ability to recite the heap pop.

9Where this shows up#

• Shortest path is a staple of the hard graph rounds at Google, Amazon, and Meta.
• It is common in the on-sites at Uber, Lyft, and DoorDash, plus anyone doing routing, logistics, or maps.
• Trading and fintech shops love Bellman-Ford because of the currency-arbitrage framing, where a negative cycle literally means free money and the V-th pass is the whole point of the question.
• Infrastructure and systems teams favor the grid and network-delay variants, since those map onto packet routing and latency.
• If a company does anything with maps, delivery, or networks, expect at least one shortest-path question somewhere in the loop.

Want to see exactly which companies lean on this pattern and in which rounds? Check the company guides for the real breakdown.