Dijkstra vs Bellman-Ford, step by step.

Dijkstra's algorithm and Bellman-Ford both find shortest paths from one vertex. Dijkstra, in O((V + E) log V), takes the closest vertex each time and never looks back, so a negative weight can make it wrong. Bellman-Ford checks every edge up to V − 1 times, in O(V·E), and handles negative weights. Use Dijkstra unless some weight is negative.

Below, both run step by step on one small graph with a negative edge: first Dijkstra goes wrong, then Bellman-Ford gets it right.

Dijkstra vs Bellman-Ford: what differs

One graph, one negative edge

Take four vertices at the corners of a square and four directed edges: A → B weighs 2, A → C weighs 4, B → D weighs 1 and C → B weighs −3. Start at A. The shortest path to D is A → C → B → D, which weighs 4 + (−3) + 1 = 2. Does Dijkstra's algorithm find it?

Here is Dijkstra's algorithm in its most common form, which looks only at the neighbors still waiting in the priority queue. Nothing in it mentions negative weights, so let it run on this graph as it is:

dijkstra(source)
    for each vertex v
        distance[v] = infinity
        predecessor[v] = none
    distance[source] = 0
    pQ = every vertex, by distance

    while pQ is not empty
        u = pQ.pollSmallest()
        for each neighbor n of u that is still in pQ
            alt = distance[u] + w(u, n)
            if alt < distance[n]
                distance[n] = alt
                predecessor[n] = u
                pQ.update(n, alt)

Dijkstra's algorithm on a graph with a negative edge

All steps as text
  1. Find the shortest paths from A to all vertices in the directed graph using Dijkstra's algorithm.
  2. Use the table to track distances from A to every vertex. Unknown distances are marked as ∞.
  3. Start from vertex A.
  4. Check distances to A's neighbors.
  5. Compute the distance from A to B: 2.
  6. Record 2 as AB's distance and set A as B's predecessor. Update the distance and predecessor if a shorter route to B is found later.
  7. Compute the distance from A to C: 4.
  8. Record 4 as AC's distance and set A as C's predecessor. Update the distance and predecessor if a shorter route to C is found later.
  9. Mark vertex A as inspected.
  10. Select B next; it is closest to A according to the table.
  11. Explore distances from B to its uninspected neighbors.
  12. The neighboring vertices.
  13. Compute the distance from B to D: 1.
  14. With BD known, set AD to 3 (combine AB's 2 and BD's 1) and update the table.
  15. Mark vertex B as inspected.
  16. Inspect D next; it has the shortest distance from A among uninspected vertices.
  17. Explore distances from D to its uninspected neighbors.
  18. Vertex D has no reachable neighbors.
  19. Mark vertex D as inspected.
  20. Inspect C next; it has the shortest distance from A among uninspected vertices.
  21. Explore distances from C to its uninspected neighbors.
  22. All reachable neighbors of C are already inspected. Skip paths through C and continue.
  23. Mark vertex C as inspected.
  24. Every vertex is inspected. Read Dijkstra's path from A to D back from the table, through the predecessors.
  25. Vertex B is identified as the predecessor of D.
  26. Vertex A is identified as the predecessor of B.
  27. Draw the path from A to D that Dijkstra's table gives.
  28. Dijkstra's path, A → B → D, is drawn. It weighs 2 + 1 = 3.
  29. Stop. There is a lighter path: A → C → B → D weighs 4 + (-3) + 1 = 2, less than Dijkstra's 3.
  30. This step is not Dijkstra's: erase its drawn path.
  31. Draw the lighter path, A → C → B → D.
  32. The lighter path, A → C → B → D, is drawn. Dijkstra missed it.
  33. Dijkstra's table still says B 2 and D 3. It never checked C → B: by the time C was inspected, B had already left the queue.
Dijkstra vs Bellman-Ford — Dijkstra's algorithm on a graph with a negative edge. Last step: Dijkstra's table still says B 2 and D 3. It never checked C → B: by the time C was inspected, B had already left the queue.

The last steps are the page's check, not Dijkstra's: after its answer, A → B → D weighing 3, the player erases that path and draws the lighter A → C → B → D, weighing 2. The table keeps Dijkstra's answer. In the captions and under the table, a pair such as AD stands for D's distance from A, not an edge: the square has no edge A → D.

Why Dijkstra fails with negative weights

What it relies on. Each time, Dijkstra takes the closest vertex not yet inspected and treats its distance as final. It never comes back to that vertex; it only uses its edges to update the neighbors. That is safe when no weight is negative: any other route to the vertex passes through a vertex that is at least as far, and from there it can only add weight. The closest vertex now is the closest for good.

What a negative edge breaks. A negative edge lets a route get cheaper by going further. Here B is taken at 2 while C is still at 4, because every other route to B goes through C, which is farther away. But C → B weighs −3, so the route through C costs 4 + (−3) = 1. By the time C is inspected, B is final, its edge to D has been used, and D has 3, computed from the old B.

The result. Dijkstra is greedy: closest first, never look back. Never looking back is safe only while a path cannot get cheaper by taking more edges.

Sometimes Dijkstra is right anyway

Change two weights: A → B 5 and A → C 1. Now C is closer than B, so C is inspected first, and C → B lowers B to −2 while B is still in the queue. Dijkstra finds every shortest path, negative edge and all.

Dijkstra's algorithm when the negative edge comes in time

All steps as text
  1. Find the shortest paths from A to all vertices in the directed graph using Dijkstra's algorithm.
  2. Use the table to track distances from A to every vertex. Unknown distances are marked as ∞.
  3. Start from vertex A.
  4. Check distances to A's neighbors.
  5. Compute the distance from A to B: 5.
  6. Record 5 as AB's distance and set A as B's predecessor. Update the distance and predecessor if a shorter route to B is found later.
  7. Compute the distance from A to C: 1.
  8. Record 1 as AC's distance and set A as C's predecessor. Update the distance and predecessor if a shorter route to C is found later.
  9. Mark vertex A as inspected.
  10. Select C next; it is closest to A according to the table.
  11. Explore distances from C to its uninspected neighbors.
  12. The neighboring vertices.
  13. Compute the distance from C to B: -3.
  14. Shorten AB to -2 via CB (add AC's 1 and CB's -3) and update the table.
  15. Mark vertex C as inspected.
  16. Inspect B next; it has the shortest distance from A among uninspected vertices.
  17. Explore distances from B to its uninspected neighbors.
  18. The neighboring vertices.
  19. Compute the distance from B to D: 1.
  20. With BD known, set AD to -1 (combine AB's -2 and BD's 1) and update the table.
  21. Mark vertex B as inspected.
  22. Inspect D next; it has the shortest distance from A among uninspected vertices.
  23. Explore distances from D to its uninspected neighbors.
  24. Vertex D has no reachable neighbors.
  25. Mark vertex D as inspected.
  26. The table provides the shortest paths from the source to all vertices. As an example, use it to obtain the shortest path from A to D.
  27. Vertex B is identified as the predecessor of D.
  28. Vertex C is identified as the predecessor of B.
  29. Vertex A is identified as the predecessor of C.
  30. Draw the shortest path from A to D.
  31. The shortest path from A to D has been successfully drawn.
  32. The shortest path from A to D, A → C → B → D, weighs 1 + (-3) + 1 = -1, and Dijkstra found it. C was inspected before B, so C → B lowered B while B was still in the queue.
Dijkstra vs Bellman-Ford — Dijkstra's algorithm when the negative edge comes in time. Last step: The shortest path from A to D, A → C → B → D, weighs 1 + (-3) + 1 = -1, and Dijkstra found it. C was inspected before B, so C → B lowered B while B was still in the queue.

Only the order differs. A negative edge does harm when the cheaper route it opens leads to a vertex that has already left the queue, and Dijkstra cannot tell in advance which case it is in. So with a negative weight it gives no guarantee: on some graphs the answer happens to be right, on others it is not.

Two versions of Dijkstra, the same weakness

Textbooks write the loop in two ways. The version above checks only neighbors still in the queue. The one in Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms checks every neighbor, for each neighbor n of u, and still takes each vertex from the queue only once. With weights of 0 or more they give the same distances, as a vertex that has left the queue never gets a shorter route. With a negative edge they differ:

Only neighbors in the queueEvery neighbor
The edge C → BNever checkedChecked: B drops from 2 to 1
On the squareB 2 and D 3, both wrongB 1, right; D 3, wrong
The square while C has its turn in the version that checks only neighbors in the queue: every vertex but C is dimmed, and so is the edge from C to B with weight -3. A, B and D carry the inspected mark. The table shows B 2 through A, C 4 through A and D 3 through B.
Only neighbors in the queue: when C's turn comes, B has already left the queue, so C → B stays gray and unchecked. The table keeps B 2 and D 3.
The same moment in the version that checks every neighbor: the edge from C to B is blue with its weight -3, and B's cell in the table now reads 1 through C. D, dimmed, still shows 3 through B.
Every neighbor: C → B is checked, and B drops to 1 through C. D keeps 3, as B → D is not checked again.

The version that checks every neighbor is right on a few more graphs, as when a negative edge leads into a vertex with no edges out, but it gives no guarantee either: lowering B after its edges were used never reaches D. Many heap-based implementations push a vertex again whenever its distance drops, and skip an entry that comes out of the queue with an older, higher distance. Such code takes B a second time and does find D = 2 here, but a vertex may then be taken many times, the running time can grow exponentially, and with a negative cycle the loop never ends.

How Bellman-Ford solves the problem

Bellman-Ford never treats a distance as final while it runs. Each pass checks every edge in a fixed order and lowers a distance whenever an edge offers a shorter route; this is called relaxing the edge. After pass k, every shortest path of up to k edges is known; a shortest path visits each vertex at most once, so it has at most V − 1 edges, and V − 1 passes are enough. It stops early after a pass that changes nothing:

bellmanFord(source)
    for each vertex v
        distance[v] = infinity
        predecessor[v] = none
    distance[source] = 0

    updated = false
    repeat V - 1 times
        updated = false
        for each edge (u, v, w)
            if distance[u] == infinity
                continue
            if distance[u] + w < distance[v]
                distance[v] = distance[u] + w
                predecessor[v] = u
                updated = true
        if not updated
            break

    if updated
        for each edge (u, v, w)
            if distance[u] != infinity and distance[u] + w < distance[v]
                return "negative cycle"
    return distance, predecessor

On the square it checks A → B, B → D, A → C and C → B, in that order. Pass 1 does what Dijkstra did, B 2 and then D 3, and after that C → B lowers B to 1. Pass 2 checks B → D again and lowers D to 2: the step Dijkstra never took. Pass 3, the last one, changes nothing, so no extra pass for negative cycles is needed.

Bellman-Ford on the same graph

All steps as text
  1. Find the shortest paths from A to all vertices in the directed graph using Bellman-Ford algorithm.
  2. Use the table to track distances from A to every vertex. Unknown distances are marked as ∞.
  3. Begin pass 1 of 3 — check all edges one by one, updating distances where a shorter path is found. The algorithm performs at most V−1 relaxation passes, where V is the number of vertices.
  4. Consider the edge from A to B.
  5. Set B's distance to 2 and record A as its predecessor.
  6. Consider the edge from B to D.
  7. With distance to B known from table, set D's distance to 3 (AB + BD = 2 + 1) and update the table.
  8. Consider the edge from A to C.
  9. Set C's distance to 4 and record A as its predecessor.
  10. Consider the edge from C to B.
  11. With distance to C known from table, a shorter path to B found (AC + CB = 4 + (-3)): update distance from 2 to 1 and set C as its predecessor.
  12. Pass 1 complete. All edges have been checked.
  13. Relaxation occurred in the previous pass — continue with pass 2 of 3.
  14. Consider the edge from A to B.
  15. Since distance to B known from table is 1, the path via A (weight of edge AB is 2) is not shorter — make no update.
  16. Consider the edge from B to D.
  17. With distance to B known from table, a shorter path to D found (AB + BD = 1 + 1): update distance from 3 to 2 and set B as its predecessor.
  18. Consider the edge from A to C.
  19. Since distance to C via A equals the current value (4) — make no update.
  20. Consider the edge from C to B.
  21. Since distance to B via C equals the current value (AC + CB = 4 + (-3)) — make no update.
  22. Pass 2 complete. All edges have been checked.
  23. Relaxation occurred in the previous pass — continue with pass 3 of 3.
  24. Consider the edge from A to B.
  25. Since distance to B known from table is 1, the path via A (weight of edge AB is 2) is not shorter — make no update.
  26. Consider the edge from B to D.
  27. Since distance to D via B equals the current value (AB + BD = 1 + 1) — make no update.
  28. Consider the edge from A to C.
  29. Since distance to C via A equals the current value (4) — make no update.
  30. Consider the edge from C to B.
  31. Since distance to B via C equals the current value (AC + CB = 4 + (-3)) — make no update.
  32. Pass 3 complete. No distance changed, so the shortest paths are final.
  33. Use the table to build the shortest path from A to D as an example — the table provides the shortest path from A to any vertex in the graph.
  34. Vertex B is identified as the predecessor of D.
  35. Vertex C is identified as the predecessor of B.
  36. The shortest path from A to D is completely defined.
  37. Draw the shortest path between these vertices to visualize the result.
  38. The shortest path from A to D has been successfully drawn.
  39. The shortest path from A to D, A → C → B → D, weighs 4 + (-3) + 1 = 2. Pass 2 checked B → D again after B had dropped to 1, which Dijkstra never did.
Dijkstra vs Bellman-Ford — Bellman-Ford on the same graph. Last step: The shortest path from A to D, A → C → B → D, weighs 4 + (-3) + 1 = 2. Pass 2 checked B → D again after B had dropped to 1, which Dijkstra never did.

Dijkstra vs Bellman-Ford at a glance

DijkstraBellman-Ford
IdeaInspect the closest vertex once and keep its distanceCheck every edge, pass after pass
Negative weightsNo guaranteeHandled
Negative cycleNot detectedDetected by one extra pass
TimeO((V + E) log V) with a binary heapO(V·E)
Extra spaceO(V): distances, predecessors, the queueO(V): distances and predecessors
Edges checked on the square3, and C → B never12, in three passes
Distance to D on the square3, wrong2
Typical usesRoad maps, link-state routing (OSPF), gamesDistance-vector routing (RIP), currency arbitrage

Negative cycles: what only Bellman-Ford reports

A negative cycle is a cycle whose weights add up to less than 0. Each lap lowers the total again, so if the source can reach the cycle, the vertices on it, and every vertex reachable from it, have no shortest path. After V − 1 passes no distance can fall unless such a cycle can be reached from the source, so the code above runs one more pass when the last one still changed something, and a distance that falls again reports the cycle. In an undirected graph one negative edge is already a negative cycle, crossed there and back.

Dijkstra vs Bellman-Ford time complexity

With a binary heap, Dijkstra takes each vertex from the queue once and lowers a distance at most once per edge, each step O(log V): O((V + E) log V). A plain array gives O(V2), better on dense graphs. Bellman-Ford makes up to V − 1 passes over all E edges: O(V·E). With 10,000 vertices and 50,000 edges, that is about 800,000 heap steps for Dijkstra against up to 500 million edge checks for Bellman-Ford, though early termination usually cuts the passes short. Both need O(V) extra space.

When to use Dijkstra and when to use Bellman-Ford

Use Dijkstra whenever no weight is negative: road lengths and travel times, link-state routing such as OSPF, and pathfinding in games, where A* is Dijkstra guided by an estimate of the distance left.

Use Bellman-Ford when some weights are negative or a negative cycle must be found: costs that can be gains, currency arbitrage with each rate r as the weight −log r, distance-vector routing such as RIP, and the first step of Johnson's algorithm for all pairs.

On a graph with no cycle, neither is needed: relaxing each vertex's edges once, in topological order, gives the shortest paths in O(V + E), negative weights included.

Common mix-ups

  • Adding a constant to every weight lets Dijkstra handle negative ones. Routes with more edges get more added. With A → B −2, B → C −2 and A → C −3, the shortest route to C is A → B → C, at −4, but after adding 3 to each weight the direct edge, at 0, wins.
  • Bellman-Ford always makes V − 1 passes. That is the most it needs: it stops after the first pass that changes nothing. On the six-vertex graph of the Bellman-Ford topic, pass 3 of 5 changes nothing, and passes 4 and 5 are skipped.

Dijkstra vs Bellman-Ford interview questions

Why doesn't Dijkstra's algorithm work with negative weights?

It treats a vertex as final as soon as it is the closest one left. A negative edge found later, from a vertex that was farther, can still lead to that vertex more cheaply, but Dijkstra never takes that vertex again, so the distances computed from it stay too high.

Can Dijkstra give the right answer on a graph with a negative edge?

Sometimes: when each vertex already has its shortest distance by the time it leaves the queue, as on the square with A → B 5 and A → C 1. It gives no guarantee, so it should not be used with negative weights.

How does Bellman-Ford detect a negative cycle?

After V − 1 passes the distances are final unless a negative cycle can be reached from the source. If one more pass still lowers a distance, such a cycle exists.

A square here.
Both algorithms in the app.

In VisiGrab, Dijkstra and Bellman-Ford each have a topic with four example graphs, and the Graph Constructor runs either one on a graph you draw.

Four graphs each

Dijkstra fills its distance table on four graphs from A to F, a check mark on each inspected vertex. Bellman-Ford counts its passes on four more, and two of them hold a negative cycle, which the app draws.

Your graph, either algorithm

In the Graph Constructor, draw a directed graph of up to 12 vertices, tap Apply, then a start and an end vertex. Dijkstra takes weights from 1 to 99, Bellman-Ford from −99 to 99 and names the vertices of a negative cycle.

Theory for both

Dijkstra's info dialog compares the running times by the queue used and says why negative weights call for Bellman-Ford. Bellman-Ford's defines relaxation, explains the early exit and covers negative cycles.

Python, Java and C++

Both algorithms in all three languages, each listing with its key points and a link to the full source on GitHub.

Two quizzes

Eight questions on Dijkstra and seven on Bellman-Ford, with an explanation for every option.

More graph algorithms

Topological sort, Prim, Kruskal, union-find, BFS and DFS each have a topic of their own.

Fast or flexible,
on one graph.

Download VisiGrab to watch both algorithms fill their distance tables, then draw a graph with negative weights and run Bellman-Ford on it.

Dijkstra and Bellman-Ford each have a topic among 30+. See them all