Dijkstra vs Bellman-Ford: When the Greedy Shortcut Fails

Dijkstra and Bellman-Ford answer the same question — the cheapest route from one node to every other on a weighted graph — and most of the time they return identical numbers. The interesting part is the one situation where they do not, because it tells you exactly what Dijkstra is betting on and why the slower algorithm exists at all.

The problem it solves

Once edges carry costs, the fewest-hops answer from breadth-first search stops being the cheapest one. Two routes of three edges can differ wildly in total, and a five-edge route can beat a one-edge route. You need an algorithm that compares sums, not hop counts.

Both algorithms use the same primitive, relaxation: if reaching u costs d and the edge u → v costs w, then v can be reached for d + w, and if that beats what you had for v, you write it down. The two algorithms differ only in which edges they relax, and when they stop.

The intuition

Dijkstra makes a greedy bet. It always expands the unfinished node with the smallest known distance and declares that distance final on the spot. The justification is a one-line argument:

Any other route to this node must leave the settled region through some node that is already at least as far away — and walking further can only add cost.

Read that sentence again and notice the hidden word: add. The argument holds only if no edge can make a route cheaper. One negative edge and a detour that looks longer at the halfway point can finish shorter. Dijkstra has already stamped the node "final" and will not look at it again.

Bellman-Ford refuses to bet. It stamps nothing. It relaxes every edge, in a full sweep, and repeats. After sweep one, every shortest path that uses one edge is correct; after sweep two, every path of up to two edges; and since a shortest path in a graph without negative cycles never repeats a node, it has at most V - 1 edges. So V - 1 sweeps are always enough.

Watch it run

The graph below has one negative edge, b → c at -3. Watch c: the sweep first reaches it directly for 5, and then the relaxation through b pulls it down to 1. Nothing was finalised early, so the cheaper number simply overwrites the older one.

The same graph, run through Dijkstra, happens to come out right — c is still unfinished when b is expanded. That is the unsettling thing about negative edges: the greedy version is not always wrong, it is unreliably right. The next example makes it fail.

The code

Four nodes. The direct edge a → b costs 2, but the detour a → c → b costs 5 + (-4) = 1. Dijkstra settles b at 2 before it ever expands c.

import heapq

INF = float("inf")
nodes = ["a", "b", "c", "d"]
edges = [("a", "b", 2), ("a", "c", 5), ("b", "d", 1), ("c", "b", -4)]
graph = {n: [] for n in nodes}
for u, v, w in edges:
    graph[u].append((v, w))

def dijkstra(src):
    dist = {n: INF for n in nodes}
    dist[src] = 0
    done, pq = set(), [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in done:
            continue
        done.add(u)                          # the greedy promise: final
        for v, w in graph[u]:
            if v not in done and d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def bellman_ford(src, edges):
    dist = {n: INF for n in nodes}
    dist[src] = 0
    for rounds in range(1, len(nodes)):      # V - 1 sweeps at most
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:                      # a quiet sweep: nothing left to learn
            break
    cycle = any(dist[u] + w < dist[v] for u, v, w in edges)
    return dist, rounds, cycle

print(dijkstra("a"))
# {'a': 0, 'b': 2, 'c': 5, 'd': 3}          b and d are wrong
print(bellman_ford("a", edges))
# ({'a': 0, 'b': 1, 'c': 5, 'd': 2}, 3, False)

loop = [("a", "b", 1), ("b", "c", 2), ("c", "b", -3), ("c", "d", 1)]
print(bellman_ford("a", loop)[2])           # True: b -> c -> b costs -1 per lap

The error in the Dijkstra output is not only at b. Because b was wrong when it was expanded, d inherited the mistake. A single bad "final" stamp propagates to everything downstream of it.

The final check in bellman_ford is the other half of the algorithm's value. After V - 1 sweeps every true shortest distance is known, so if one more sweep can still improve anything, there is no true shortest distance: some cycle has negative total weight and you can lap it forever. That second graph does exactly that.

The complexity

• Dijkstra with a binary heap: O((V + E) log V). Each node is settled once; each edge causes at most one push.
• Bellman-Ford: O(V · E). Up to V - 1 sweeps, each touching all E edges. The early exit on a quiet sweep helps in practice but does not change the worst case.

On a sparse graph with a hundred thousand nodes and as many edges, the first is a few million steps and the second is ten billion. You pay that price only when you need what Bellman-Ford buys.

Where it goes wrong

• "Just remove the done set." The heap-only version, which skips stale entries with if d > dist[u]: continue, does get this small example right, because it re-expands b when the cheaper value arrives. But it has quietly stopped being Dijkstra: nodes can be expanded many times, and on adversarial graphs the running time can blow up exponentially. It is a correctness patch that throws away the complexity guarantee.
• "Just add a constant to every weight." Shifting every edge by +4 makes all weights non-negative but penalises routes by their number of edges, so a many-hop route that was cheapest may lose. The reweighting that does work — Johnson's algorithm — uses node potentials computed by one Bellman-Ford run, not a flat constant.
• Negative cycles in Dijkstra. It will not detect them; it just returns a number. Only an algorithm that keeps relaxing can notice that relaxing never stops.
• Undirected negative edges. An undirected edge of weight -1 is itself a negative cycle — go across and come back. Most shortest-path questions with negative weights are therefore on directed graphs.

How to say it in an interview

Lead with the assumption, not the algorithm names:

"Dijkstra is greedy: when it pops the nearest unfinished node it declares that distance final, which is only safe because extending a path can never make it cheaper. With non-negative weights I would use it — O((V + E) log V) with a heap. If any weight can be negative, that argument breaks, so I would use Bellman-Ford: relax every edge V - 1 times, O(V · E), and one extra sweep that still improves a distance means a negative cycle."

Then name the practical examples where negative weights show up — rebates on some routes, or currency conversion rates turned into weights with a negative logarithm, where a negative cycle means an arbitrage loop. It shows you know why the slower algorithm is not academic.