Medium Problemsgraphminimization

Bellman–Ford Algorithm

Find the shortest distance from one source vertex to every other vertex in a weighted directed graph that may contain negative edge weights, and report whether a negative cycle exists.

Note. Filed under Medium in the course's source list. It is a graph relaxation algorithm rather than textbook tabulation, though its layer-by-layer relaxation is genuinely a DP over 'shortest path using at most k edges'.

Do this lesson first: coin change

Example input

5 vertices, source 0, edges 0→1 (6), 0→3 (7), 1→2 (5), 1→3 (8), 1→4 (-4), 2→1 (-2), 3→2 (-3), 3→4 (9), 4→0 (2), 4→2 (7)

Expected output

distances 0, 2, 4, 7, -2; no negative cycle

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[k][v] = min(dp[k - 1][v], min over edges u→v of dp[k - 1][u] + w(u, v))

Take the cheapest walk to v with at most k edges and ask about its last edge. Either it does not need the k-th edge at all, and it is already dp[k - 1][v]; or its last edge is some u→v, and the walk up to u is a walk with at most k - 1 edges, so swapping in the cheapest such walk, dp[k - 1][u], can only help. So the cell is the best of staying put and every incoming edge. It is the coin-change lesson's shape: a minimum over the last choice made, a coin there and an incoming edge here, each pointing at a smaller subproblem plus a cost. That lesson derives the pattern; this page assumes it.

Row 0 allows no edges, so only the source is reachable: 0 there and ∞ everywhere else. Each row reads only the row above, so the table fills one whole row at a time, which is exactly one round of relaxation. On 5 vertices, row 4 is final when there is no negative cycle: a cheapest walk then never needs to repeat a vertex, so it uses at most 4 edges. Row 5 is the check: if any cell there is lower than the one above it, a walk with 5 edges beat every walk with at most 4, which means it repeated a vertex and gained by going round a cycle, a negative one.

Tabulation, row by row: V rounds over E edges, O(V × E). The table keeps every round so you can watch distances settle, but each row reads only the one above, so two rows are enough, and the usual code keeps a single array and relaxes in place. In place, a round's values can only get smaller sooner: each is still the cost of a real walk, possibly one with more than k edges. The final distances and the check are unaffected, but a row no longer means "at most k edges". A round that changes nothing means nothing will change again, so real implementations stop early.

Time O(V × E)Space O(V²) for the table, O(V) with one array

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 allows no edges, so only the source is reachable: 0 there and ∞ everywhere else. Each row reads only the row above, so the table fills one whole row at a time, which is exactly one round of relaxation. On 5 vertices, row 4 is final when there is no negative cycle: a cheapest walk then never needs to repeat a vertex, so it uses at most 4 edges. Row 5 is the check: if any cell there is lower than the one above it, a walk with 5 edges beat every walk with at most 4, which means it repeated a vertex and gained by going round a cycle, a negative one.

Graph

A: all weights positiveB: negative edgesC: negative cycles

Source 0. Edges: 0→1 (6), 0→3 (7), 1→2 (5), 1→3 (8), 1→4 (-4), 2→1 (-2), 3→2 (-3), 3→4 (9), 4→0 (2), 4→2 (7). (A with 1→4, 2→1 and 3→2 made negative.)

The walkthrough uses this input. Finish it to unlock the others.

Rows ↓
Cols →

0

1

2

3

4

k=0

0

∞

k=1

0

6

∞

7

∞

k=2

0

6

4

7

2

k=3

0

2

4

7

2

k=4

0

2

4

7

-2

check

0

2

4

7

-2

Rows ↓edges allowed (k)

Cols →vertex: cheapest walk from vertex 0

bellman-ford.ts

1function bellmanFord(n, edges, src) {
2 const dp = [new Array(n).fill(Infinity)];
3 dp[0][src] = 0;
4 for (let k = 1; k <= n; k++) { // round n is the check
5 dp[k] = [...dp[k - 1]];
6 for (const [u, v, w] of edges) {
7 dp[k][v] = Math.min(dp[k][v], dp[k - 1][u] + w);
8 }
9 }
10 const negativeCycle = dp[n].some((d, v) => d < dp[n - 1][v]);
11 return { dist: dp[n - 1], negativeCycle };
12}

Base caseComputedBeing readAnswer

The code, the trap, the variations

bellman-ford.ts

1function bellmanFord(n, edges, src) {
2 const dp = [new Array(n).fill(Infinity)];
3 dp[0][src] = 0;
4 for (let k = 1; k <= n; k++) { // round n is the check
5 dp[k] = [...dp[k - 1]];
6 for (const [u, v, w] of edges) {
7 dp[k][v] = Math.min(dp[k][v], dp[k - 1][u] + w);
8 }
9 }
10 const negativeCycle = dp[n].some((d, v) => d < dp[n - 1][v]);
11 return { dist: dp[n - 1], negativeCycle };
12}

Where people go wrong

Stopping after V - 1 rounds and reporting row V - 1 without the check. On graph C that reports -6 as the distance to vertex 4, but row 5 is lower again in three of the five columns. The graph has negative cycles, the cheapest being 0 → 3 → 2 → 1 → 4 → 0 at -4, and that one passes through every vertex, so a walk can go round it as often as it likes: no vertex has a shortest distance, not even vertex 4, whose column happens to hold still for one round. The second trap shows up when ∞ is stored as a large number such as 1e9: 1e9 + (-4) is smaller than 1e9, so an unreachable vertex looks reachable after one round. Skip any edge whose start is still ∞, which is what JavaScript's Infinity does for free.

Cheapest route with at most K stops, so at most K + 1 edges.
Nothing in the recurrence changes. Fill rows up to K + 1 and read that row; the limit is the layer index this table already has. Relaxing in place breaks this version, because in place a round can use more than one new edge.
Cheapest walk with EXACTLY k edges.
Drop the dp[k - 1][v] candidate, so a cell must arrive over an edge in this round; row 0 is unchanged.
All weights are non-negative.
The table is still correct, and the check row can never move. Dijkstra's algorithm then answers the same question in O(E log V), because a finished vertex can never be improved.

Maximum size square sub-matrix with all 1s Floyd Warshall Algorithm