Why Dijkstra fails with negative weights

Graphs Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Edges: A→B 2, A→C 3, C→B -2. Dijkstra from A settles B at 2 first. What is wrong?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A The route A→C→B costs 1, which is cheaper than the settled 2

Right: the negative edge makes a later route cheaper.

Settling assumes distances only grow along a route, which a negative edge breaks.

Why not the others?
  • B B should be settled at 3. The true shortest distance to B is 1.
  • C Nothing; Dijkstra handles this case. Once B is settled it is never revised, so the answer stays 2.

30-second answer

Dijkstra settles the closest unsettled node and never revisits it, assuming no later route can be cheaper. A negative edge breaks that: a longer-looking route can drop below a settled distance after the fact. Bellman-Ford relaxes every edge V - 1 times in O(V·E), handles negative weights and detects negative cycles.

Practise saying it · 45 s. No recording, just a timer

Explain Dijkstra's non-negative requirement.

Say your answer out loud, then check which of these points you covered:

  • Settled nodes never change
  • Negative edges break that
  • Bellman-Ford O(V·E)

Deep dive

For DAGs, relax edges in topological order: O(V + E) even with negative weights.

With only 0 and 1 weights, 0-1 BFS with a deque is O(V + E).

Adding a constant to every edge does not fix negative weights; it favours routes with fewer edges.

Common mistakes

  • Adding a big constant to every weight to make them positive.
  • Assuming Dijkstra just 'runs slower' with negatives; it gives wrong answers.

Senior take & follow-ups

Give the two-line counterexample: A→B costs 2, A→C costs 3, C→B costs -2.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is a negative cycle?

    Show hint

    A loop whose total weight is negative; shortest paths are then undefined.

  2. How do you detect one with Bellman-Ford?

    Show hint

    If a V-th round still improves a distance, a negative cycle is reachable.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

Try it in a free tool

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.