Comparisons and explanations · Intermediate

Dijkstra versus Bellman–Ford

Compare nonnegative-weight greedy finalization with repeated relaxation, including reachable negative cycles, early exit and implementation costs.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. The weight assumptions differ
  2. Dijkstra finalizes the smallest valid candidate
  3. Bellman–Ford expands the permitted path length
  4. Identify which vertices a negative cycle affects
  5. Compare cost and early-termination rules
  6. Ask Logeia about this articleCheck your understanding

The weight assumptions differ

Dijkstra and Bellman–Ford both address shortest distances from a source in a weighted graph. Standard Dijkstra relies on nonnegative edge weights. Bellman–Ford can handle negative edges but needs to identify reachable negative cycles and the vertices they affect. A negative edge is not the same thing as a negative cycle. Both methods use relaxation to improve candidate distances through edges; neither is simply a traversal-order listing. Before selecting one, specify allowed weights and the desired output, including how unreachable vertices and unbounded distances should be represented. The word shortest is incomplete without those conditions, and using the faster-looking method outside its assumptions can invalidate the result rather than merely slow it down.

AspectStandard DijkstraBellman–Ford
WeightsRequires nonnegative edgesHandles negative edges
Main ruleFinalize minimum valid candidateRepeat relaxation over edges
Negative cyclesOutside assumptionsClassify reachability and effects

Dijkstra finalizes the smallest valid candidate

With A→B=4, A→C=1 and C→B=2, processing C at tentative distance one improves B from four to three. Nonnegative edges justify finalizing the smallest valid tentative distance: a route through a more distant unfinished vertex cannot later reduce it by adding nonnegative cost. A negative edge breaks that argument. For A→B=1, A→C=2 and C→B=−3, finalizing B at one would precede discovery of a path costing minus one. No negative cycle is needed for that counterexample. Some implementations can revisit vertices, but changing their rule changes the algorithm and its analysis; it does not justify the usual Dijkstra guarantee on arbitrary negative edges.

Bellman–Ford expands the permitted path length

Bellman–Ford repeatedly relaxes all edges, considering routes that can use progressively more edges. Without a reachable negative cycle, a shortest path can be chosen without repeated vertices, requiring at most V−1 edges. That yields the familiar bound of V−1 passes. An implementation updating distances in place can propagate improvement across several edges during one pass, depending on edge order. Therefore an explanation claiming that each intermediate array represents exactly a particular edge-count bound must specify whether it uses separate previous and next arrays or in-place updates. Keep the proof model and code consistent. The final correctness argument is related, but intermediate-state descriptions should not silently assume a different implementation.

Identify which vertices a negative cycle affects

If a reachable distance can still be improved after V−1 passes, that indicates the effect of a reachable negative cycle under the algorithm’s conditions. Repeating such a cycle can lower path cost indefinitely for affected downstream vertices, so a finite minimum must not be reported for them. A negative cycle unreachable from the source does not have that same effect on this source’s distances. Nor should every vertex automatically be marked unbounded merely because one reachable negative cycle exists: propagation follows graph reachability from the affected region. Distinguish finite distance, unreachable state and lack of a lower bound. Those outcomes mean different things to a caller attempting to recover or use a route.

Compare cost and early-termination rules

With adjacency lists and a suitable heap, Dijkstra has familiar bounds such as O((V+E)log V); lazy duplicate-candidate implementations require attention to queue size. Standard Bellman–Ford has O(VE) worst-case time, although a pass with no improvement can permit earlier termination. For target-specific Dijkstra, stop when the target is removed with its smallest valid distance, not when first discovered. Implementations also need defined representations for infinity and unreachable vertices, safe addition and checks for overflow or inappropriate numeric values. A speed comparison is useful only after those input and termination contracts are correct. Faster output under an invalid weight assumption is not a valid replacement for the required shortest-path result.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path