PK

PKBytes

Explore tracks
Chapter 35: Shortest Paths and Weighted Graph Search
35.04Intermediate / Advanced4 topics16 min4 interactive animations

Bellman-Ford

Bellman-Ford relaxes every edge in repeated passes: after k passes all shortest paths of at most k edges are correct, so n - 1 passes suffice, and one more pass reveals a reachable negative cycle.

Learning goals

  • Run Bellman-Ford and say why n - 1 passes are enough
  • Stop early when a pass changes nothing
  • Detect a negative cycle and extract it
  • Separate vertices with distance minus infinity from the rest

Prerequisites

Shortest path framework

Dijkstra fails with negative edges, and negative edges are real: currency exchange, energy gains, refunds. Bellman-Ford handles them, at the price of O(n · m) time, and it tells you when the question has no answer.

35.04.1

Negative edges

Bellman-Ford does not rely on any order of vertices. It relaxes **every** edge, in any order, and repeats this pass. The negative weights do no harm because no distance is ever declared final until the end. In the first preset a negative edge lowers a distance that an earlier pass had already set.

The result is null (or a flag) when a negative cycle is reachable from the source. The first branch of the animation shows the passes edge by edge, with the current distances beside each vertex.

Java
1static long[] bellmanFord(int n, int[][] edges, int s) {         // edges {u, v, w}; null on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    Arrays.fill(dist, INF);
5    dist[s] = 0;
6    for (int round = 1; round < n; round++) {                     // a shortest path has at most n - 1 edges
7        boolean changed = false;
8        for (int[] e : edges)
9            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
10        if (!changed) break;                                      // nothing improved: finished early
11    }
12    for (int[] e : edges)                                         // one more pass: any improvement means a negative cycle
13        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
14    return dist;
15}

Bellman-Ford and SPFA: shortest paths with negative edges and cycle detection

Interactive · edit the input

Your input

Try

directed graph · 5 vertices · 9 edges

0

d=0

1
2
3
4
Edge / vertex being processedIn the queueTree edge (on a best path)Edge that still improves: negative cycle

dist[v]

00
∞1
∞2
∞3
∞4
Setup

dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.

Step 1 / 32
Java
1long[] bellmanFord(int n, int[][] edges, int s) {   // edges: {u, v, w}; null on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    for (int round = 1; round < n; round++) {     // a shortest path has at most n - 1 edges
5        boolean changed = false;
6        for (int[] e : edges)
7            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
8        if (!changed) break;                      // nothing improved: finished early
9    }
10    for (int[] e : edges)                         // one more pass: any improvement means a negative cycle
11        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
12    return dist;
13}
14long[] spfa(int n, List<int[]>[] adj, int s) {    // adj[u] = {v, w}; null on a reachable negative cycle
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
17    int[] len = new int[n]; boolean[] inQ = new boolean[n];
18    Deque<Integer> q = new ArrayDeque<>(); q.add(s); inQ[s] = true;
19    while (!q.isEmpty()) {
20        int u = q.poll(); inQ[u] = false;
21        for (int[] e : adj[u]) {
22            if (dist[u] + e[1] >= dist[e[0]]) continue;
23            dist[e[0]] = dist[u] + e[1]; len[e[0]] = len[u] + 1;
24            if (len[e[0]] >= n) return null;      // a best path with n edges repeats a vertex
25            if (!inQ[e[0]]) { q.add(e[0]); inQ[e[0]] = true; }
26        }
27    }
28    return dist;
29}

Live state

0 relaxations0 edges examined

source

0

No condition evaluated on this step
Execution trace (dry run table)Show 32 steps
StepLineStateWhat happens
1L3source=0dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.
2L7round=1 u=0 v=1 dist[v]=6Round 1, 0 → 1: 0 + 6 = 6 is better, so dist[1] = 6.
3L7round=1 u=0 v=2 dist[v]=7Round 1, 0 → 2: 0 + 7 = 7 is better, so dist[2] = 7.
4L7round=1 edge=1 → 2 candidate=14Round 1, 1 → 2: 6 + 8 = 14 is not better than 7: no change.
5L7round=1 u=1 v=3 dist[v]=11Round 1, 1 → 3: 6 + 5 = 11 is better, so dist[3] = 11.
6L7round=1 u=1 v=4 dist[v]=2Round 1, 1 → 4: 6 + -4 = 2 is better, so dist[4] = 2.
7L7round=1 u=2 v=3 dist[v]=4Round 1, 2 → 3: 7 + -3 = 4 is better, so dist[3] = 4.
8L7round=1 edge=2 → 4 candidate=16Round 1, 2 → 4: 7 + 9 = 16 is not better than 2: no change.
9L7round=1 u=3 v=1 dist[v]=2Round 1, 3 → 1: 4 + -2 = 2 is better, so dist[1] = 2.
10L7round=1 edge=4 → 3 candidate=9Round 1, 4 → 3: 2 + 7 = 9 is not better than 4: no change.
11L9round=1 dist=[0, 2, 7, 4, 2]End of round 1: distances [0, 2, 7, 4, 2]. Paths with up to 1 edges are now correct.
12L7round=2 edge=0 → 1 candidate=6Round 2, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
13L7round=2 edge=0 → 2 candidate=7Round 2, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
14L7round=2 edge=1 → 2 candidate=10Round 2, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
15L7round=2 edge=1 → 3 candidate=7Round 2, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
16L7round=2 u=1 v=4 dist[v]=-2Round 2, 1 → 4: 2 + -4 = -2 is better, so dist[4] = -2.
17L7round=2 edge=2 → 3 candidate=4Round 2, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
18L7round=2 edge=2 → 4 candidate=16Round 2, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
19L7round=2 edge=3 → 1 candidate=2Round 2, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
20L7round=2 edge=4 → 3 candidate=5Round 2, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
21L9round=2 dist=[0, 2, 7, 4, -2]End of round 2: distances [0, 2, 7, 4, -2]. Paths with up to 2 edges are now correct.
22L7round=3 edge=0 → 1 candidate=6Round 3, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
23L7round=3 edge=0 → 2 candidate=7Round 3, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
24L7round=3 edge=1 → 2 candidate=10Round 3, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
25L7round=3 edge=1 → 3 candidate=7Round 3, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
26L7round=3 edge=1 → 4 candidate=-2Round 3, 1 → 4: 2 + -4 = -2 is not better than -2: no change.
27L7round=3 edge=2 → 3 candidate=4Round 3, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
28L7round=3 edge=2 → 4 candidate=16Round 3, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
29L7round=3 edge=3 → 1 candidate=2Round 3, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
30L7round=3 edge=4 → 3 candidate=5Round 3, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
31L9round=3Round 3 changed nothing, so no later round can: stop early.
32L12return=[0, 2, 7, 4, -2] relaxations=7No edge improves in the check pass: no negative cycle is reachable. Distances: [0, 2, 7, 4, -2]. Cost O(n · m).
35.04.2

Repeated relaxation

**Why n - 1 passes?** After pass k, every vertex whose shortest path has at most k edges has its correct distance (by induction: the last edge of such a path is relaxed in pass k, after its tail was correct from pass k - 1). A shortest path with no repeated vertex has at most n - 1 edges, so n - 1 passes finish the job when there is no negative cycle.

A pass may fix more than one edge of a path if the edges are processed in a lucky order, so fewer passes can be enough. The function below counts the passes that changed something; if a pass changes nothing, no later pass can, and you can stop. In the worst case the order of edges is unlucky and all n - 1 passes are needed.

Java
1static int passesUntilStable(int n, int[][] edges, int s) {       // passes that changed something; -1 on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    Arrays.fill(dist, INF);
5    dist[s] = 0;
6    int passes = 0;
7    for (int round = 1; round <= n; round++) {
8        boolean changed = false;
9        for (int[] e : edges)
10            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
11        if (!changed) return passes;
12        if (round == n) return -1;                                // pass n still improves: a negative cycle
13        passes++;
14    }
15    return passes;
16}

Bellman-Ford and SPFA: shortest paths with negative edges and cycle detection

Interactive · edit the input

Your input

Try

directed graph · 5 vertices · 9 edges

0

d=0

1
2
3
4
Edge / vertex being processedIn the queueTree edge (on a best path)Edge that still improves: negative cycle

dist[v]

00
∞1
∞2
∞3
∞4
Setup

dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.

Step 1 / 32
Java
1long[] bellmanFord(int n, int[][] edges, int s) {   // edges: {u, v, w}; null on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    for (int round = 1; round < n; round++) {     // a shortest path has at most n - 1 edges
5        boolean changed = false;
6        for (int[] e : edges)
7            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
8        if (!changed) break;                      // nothing improved: finished early
9    }
10    for (int[] e : edges)                         // one more pass: any improvement means a negative cycle
11        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
12    return dist;
13}
14long[] spfa(int n, List<int[]>[] adj, int s) {    // adj[u] = {v, w}; null on a reachable negative cycle
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
17    int[] len = new int[n]; boolean[] inQ = new boolean[n];
18    Deque<Integer> q = new ArrayDeque<>(); q.add(s); inQ[s] = true;
19    while (!q.isEmpty()) {
20        int u = q.poll(); inQ[u] = false;
21        for (int[] e : adj[u]) {
22            if (dist[u] + e[1] >= dist[e[0]]) continue;
23            dist[e[0]] = dist[u] + e[1]; len[e[0]] = len[u] + 1;
24            if (len[e[0]] >= n) return null;      // a best path with n edges repeats a vertex
25            if (!inQ[e[0]]) { q.add(e[0]); inQ[e[0]] = true; }
26        }
27    }
28    return dist;
29}

Live state

0 relaxations0 edges examined

source

0

No condition evaluated on this step
Execution trace (dry run table)Show 32 steps
StepLineStateWhat happens
1L3source=0dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.
2L7round=1 u=0 v=1 dist[v]=6Round 1, 0 → 1: 0 + 6 = 6 is better, so dist[1] = 6.
3L7round=1 u=0 v=2 dist[v]=7Round 1, 0 → 2: 0 + 7 = 7 is better, so dist[2] = 7.
4L7round=1 edge=1 → 2 candidate=14Round 1, 1 → 2: 6 + 8 = 14 is not better than 7: no change.
5L7round=1 u=1 v=3 dist[v]=11Round 1, 1 → 3: 6 + 5 = 11 is better, so dist[3] = 11.
6L7round=1 u=1 v=4 dist[v]=2Round 1, 1 → 4: 6 + -4 = 2 is better, so dist[4] = 2.
7L7round=1 u=2 v=3 dist[v]=4Round 1, 2 → 3: 7 + -3 = 4 is better, so dist[3] = 4.
8L7round=1 edge=2 → 4 candidate=16Round 1, 2 → 4: 7 + 9 = 16 is not better than 2: no change.
9L7round=1 u=3 v=1 dist[v]=2Round 1, 3 → 1: 4 + -2 = 2 is better, so dist[1] = 2.
10L7round=1 edge=4 → 3 candidate=9Round 1, 4 → 3: 2 + 7 = 9 is not better than 4: no change.
11L9round=1 dist=[0, 2, 7, 4, 2]End of round 1: distances [0, 2, 7, 4, 2]. Paths with up to 1 edges are now correct.
12L7round=2 edge=0 → 1 candidate=6Round 2, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
13L7round=2 edge=0 → 2 candidate=7Round 2, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
14L7round=2 edge=1 → 2 candidate=10Round 2, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
15L7round=2 edge=1 → 3 candidate=7Round 2, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
16L7round=2 u=1 v=4 dist[v]=-2Round 2, 1 → 4: 2 + -4 = -2 is better, so dist[4] = -2.
17L7round=2 edge=2 → 3 candidate=4Round 2, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
18L7round=2 edge=2 → 4 candidate=16Round 2, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
19L7round=2 edge=3 → 1 candidate=2Round 2, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
20L7round=2 edge=4 → 3 candidate=5Round 2, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
21L9round=2 dist=[0, 2, 7, 4, -2]End of round 2: distances [0, 2, 7, 4, -2]. Paths with up to 2 edges are now correct.
22L7round=3 edge=0 → 1 candidate=6Round 3, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
23L7round=3 edge=0 → 2 candidate=7Round 3, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
24L7round=3 edge=1 → 2 candidate=10Round 3, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
25L7round=3 edge=1 → 3 candidate=7Round 3, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
26L7round=3 edge=1 → 4 candidate=-2Round 3, 1 → 4: 2 + -4 = -2 is not better than -2: no change.
27L7round=3 edge=2 → 3 candidate=4Round 3, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
28L7round=3 edge=2 → 4 candidate=16Round 3, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
29L7round=3 edge=3 → 1 candidate=2Round 3, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
30L7round=3 edge=4 → 3 candidate=5Round 3, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
31L9round=3Round 3 changed nothing, so no later round can: stop early.
32L12return=[0, 2, 7, 4, -2] relaxations=7No edge improves in the check pass: no negative cycle is reachable. Distances: [0, 2, 7, 4, -2]. Cost O(n · m).
35.04.3

Negative-cycle detection

If a pass number n still improves some distance, the graph has a negative cycle reachable from the source, because otherwise n - 1 passes would already have settled everything. To *find* the cycle, remember for each vertex the edge that last improved it; starting from a vertex improved in pass n and stepping back n times along those edges lands inside the cycle, and one more lap collects it.

Starting every distance at 0 (as if a virtual source reached every vertex for free) finds a negative cycle anywhere, not only ones reachable from a chosen source. The edges are returned in order around the cycle. The *Negative cycle reachable from 0* preset ends with the check pass that fails.

Java
1static List<Integer> negativeCycleEdges(int n, int[][] edges) {   // indexes of the edges of one negative cycle, in order; empty if none
2    long[] dist = new long[n];                                    // all 0: a virtual source reaches every vertex
3    int[] viaEdge = new int[n];
4    Arrays.fill(viaEdge, -1);
5    int last = -1;
6    for (int round = 0; round < n; round++) {
7        last = -1;
8        for (int k = 0; k < edges.length; k++) {
9            int[] e = edges[k];
10            if (dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; viaEdge[e[1]] = k; last = e[1]; }
11        }
12        if (last == -1) return new ArrayList<>();                 // a pass changed nothing: no negative cycle
13    }
14    int v = last;
15    for (int i = 0; i < n; i++) v = edges[viaEdge[v]][0];         // n steps back along the improving edges lands inside the cycle
16    List<Integer> cycle = new ArrayList<>();
17    int u = v;
18    do {
19        int k = viaEdge[u];
20        cycle.add(k);
21        u = edges[k][0];
22    } while (u != v);
23    Collections.reverse(cycle);                                   // now in forward order
24    return cycle;
25}

Bellman-Ford and SPFA: shortest paths with negative edges and cycle detection

Interactive · edit the input

Your input

Try

directed graph · 5 vertices · 9 edges

0

d=0

1
2
3
4
Edge / vertex being processedIn the queueTree edge (on a best path)Edge that still improves: negative cycle

dist[v]

00
∞1
∞2
∞3
∞4
Setup

dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.

Step 1 / 32
Java
1long[] bellmanFord(int n, int[][] edges, int s) {   // edges: {u, v, w}; null on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    for (int round = 1; round < n; round++) {     // a shortest path has at most n - 1 edges
5        boolean changed = false;
6        for (int[] e : edges)
7            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
8        if (!changed) break;                      // nothing improved: finished early
9    }
10    for (int[] e : edges)                         // one more pass: any improvement means a negative cycle
11        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
12    return dist;
13}
14long[] spfa(int n, List<int[]>[] adj, int s) {    // adj[u] = {v, w}; null on a reachable negative cycle
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
17    int[] len = new int[n]; boolean[] inQ = new boolean[n];
18    Deque<Integer> q = new ArrayDeque<>(); q.add(s); inQ[s] = true;
19    while (!q.isEmpty()) {
20        int u = q.poll(); inQ[u] = false;
21        for (int[] e : adj[u]) {
22            if (dist[u] + e[1] >= dist[e[0]]) continue;
23            dist[e[0]] = dist[u] + e[1]; len[e[0]] = len[u] + 1;
24            if (len[e[0]] >= n) return null;      // a best path with n edges repeats a vertex
25            if (!inQ[e[0]]) { q.add(e[0]); inQ[e[0]] = true; }
26        }
27    }
28    return dist;
29}

Live state

0 relaxations0 edges examined

source

0

No condition evaluated on this step
Execution trace (dry run table)Show 32 steps
StepLineStateWhat happens
1L3source=0dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.
2L7round=1 u=0 v=1 dist[v]=6Round 1, 0 → 1: 0 + 6 = 6 is better, so dist[1] = 6.
3L7round=1 u=0 v=2 dist[v]=7Round 1, 0 → 2: 0 + 7 = 7 is better, so dist[2] = 7.
4L7round=1 edge=1 → 2 candidate=14Round 1, 1 → 2: 6 + 8 = 14 is not better than 7: no change.
5L7round=1 u=1 v=3 dist[v]=11Round 1, 1 → 3: 6 + 5 = 11 is better, so dist[3] = 11.
6L7round=1 u=1 v=4 dist[v]=2Round 1, 1 → 4: 6 + -4 = 2 is better, so dist[4] = 2.
7L7round=1 u=2 v=3 dist[v]=4Round 1, 2 → 3: 7 + -3 = 4 is better, so dist[3] = 4.
8L7round=1 edge=2 → 4 candidate=16Round 1, 2 → 4: 7 + 9 = 16 is not better than 2: no change.
9L7round=1 u=3 v=1 dist[v]=2Round 1, 3 → 1: 4 + -2 = 2 is better, so dist[1] = 2.
10L7round=1 edge=4 → 3 candidate=9Round 1, 4 → 3: 2 + 7 = 9 is not better than 4: no change.
11L9round=1 dist=[0, 2, 7, 4, 2]End of round 1: distances [0, 2, 7, 4, 2]. Paths with up to 1 edges are now correct.
12L7round=2 edge=0 → 1 candidate=6Round 2, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
13L7round=2 edge=0 → 2 candidate=7Round 2, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
14L7round=2 edge=1 → 2 candidate=10Round 2, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
15L7round=2 edge=1 → 3 candidate=7Round 2, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
16L7round=2 u=1 v=4 dist[v]=-2Round 2, 1 → 4: 2 + -4 = -2 is better, so dist[4] = -2.
17L7round=2 edge=2 → 3 candidate=4Round 2, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
18L7round=2 edge=2 → 4 candidate=16Round 2, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
19L7round=2 edge=3 → 1 candidate=2Round 2, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
20L7round=2 edge=4 → 3 candidate=5Round 2, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
21L9round=2 dist=[0, 2, 7, 4, -2]End of round 2: distances [0, 2, 7, 4, -2]. Paths with up to 2 edges are now correct.
22L7round=3 edge=0 → 1 candidate=6Round 3, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
23L7round=3 edge=0 → 2 candidate=7Round 3, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
24L7round=3 edge=1 → 2 candidate=10Round 3, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
25L7round=3 edge=1 → 3 candidate=7Round 3, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
26L7round=3 edge=1 → 4 candidate=-2Round 3, 1 → 4: 2 + -4 = -2 is not better than -2: no change.
27L7round=3 edge=2 → 3 candidate=4Round 3, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
28L7round=3 edge=2 → 4 candidate=16Round 3, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
29L7round=3 edge=3 → 1 candidate=2Round 3, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
30L7round=3 edge=4 → 3 candidate=5Round 3, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
31L9round=3Round 3 changed nothing, so no later round can: stop early.
32L12return=[0, 2, 7, 4, -2] relaxations=7No edge improves in the check pass: no negative cycle is reachable. Distances: [0, 2, 7, 4, -2]. Cost O(n · m).
35.04.4

Reachable negative cycles

A negative cycle only matters for vertices that can be reached *through* it. A negative cycle that the source cannot reach changes nothing (the third preset shows distances are still fine). And if only some vertices lie behind the cycle, others keep a finite distance.

To tell them apart, run n - 1 passes, mark the head of every edge that can still be improved, then spread the mark along all edges: every marked vertex has distance minus infinity. This is how contest problems ask for -INF per vertex.

Java
1static boolean[] unboundedBelow(int n, int[][] edges, int s) {    // true where the distance from s is -infinity
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    Arrays.fill(dist, INF);
5    dist[s] = 0;
6    for (int round = 1; round < n; round++)
7        for (int[] e : edges)
8            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = dist[e[0]] + e[2];
9    boolean[] bad = new boolean[n];
10    Deque<Integer> stack = new ArrayDeque<>();
11    for (int[] e : edges)                                          // an edge that still improves is on or behind a negative cycle
12        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]] && !bad[e[1]]) { bad[e[1]] = true; stack.push(e[1]); }
13    while (!stack.isEmpty()) {
14        int u = stack.pop();
15        for (int[] e : edges)
16            if (e[0] == u && !bad[e[1]]) { bad[e[1]] = true; stack.push(e[1]); }
17    }
18    return bad;
19}

Bellman-Ford and SPFA: shortest paths with negative edges and cycle detection

Interactive · edit the input

Your input

Try

directed graph · 5 vertices · 9 edges

0

d=0

1
2
3
4
Edge / vertex being processedIn the queueTree edge (on a best path)Edge that still improves: negative cycle

dist[v]

00
∞1
∞2
∞3
∞4
Setup

dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.

Step 1 / 32
Java
1long[] bellmanFord(int n, int[][] edges, int s) {   // edges: {u, v, w}; null on a reachable negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    for (int round = 1; round < n; round++) {     // a shortest path has at most n - 1 edges
5        boolean changed = false;
6        for (int[] e : edges)
7            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
8        if (!changed) break;                      // nothing improved: finished early
9    }
10    for (int[] e : edges)                         // one more pass: any improvement means a negative cycle
11        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
12    return dist;
13}
14long[] spfa(int n, List<int[]>[] adj, int s) {    // adj[u] = {v, w}; null on a reachable negative cycle
15    long INF = Long.MAX_VALUE / 2;
16    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
17    int[] len = new int[n]; boolean[] inQ = new boolean[n];
18    Deque<Integer> q = new ArrayDeque<>(); q.add(s); inQ[s] = true;
19    while (!q.isEmpty()) {
20        int u = q.poll(); inQ[u] = false;
21        for (int[] e : adj[u]) {
22            if (dist[u] + e[1] >= dist[e[0]]) continue;
23            dist[e[0]] = dist[u] + e[1]; len[e[0]] = len[u] + 1;
24            if (len[e[0]] >= n) return null;      // a best path with n edges repeats a vertex
25            if (!inQ[e[0]]) { q.add(e[0]); inQ[e[0]] = true; }
26        }
27    }
28    return dist;
29}

Live state

0 relaxations0 edges examined

source

0

No condition evaluated on this step
Execution trace (dry run table)Show 32 steps
StepLineStateWhat happens
1L3source=0dist[0] = 0 and every other distance is unknown (∞). Relaxing an edge u → v with weight w means: if dist[u] + w is smaller than dist[v], use it. A shortest path has at most n - 1 = 4 edges, so n - 1 passes over all edges are enough.
2L7round=1 u=0 v=1 dist[v]=6Round 1, 0 → 1: 0 + 6 = 6 is better, so dist[1] = 6.
3L7round=1 u=0 v=2 dist[v]=7Round 1, 0 → 2: 0 + 7 = 7 is better, so dist[2] = 7.
4L7round=1 edge=1 → 2 candidate=14Round 1, 1 → 2: 6 + 8 = 14 is not better than 7: no change.
5L7round=1 u=1 v=3 dist[v]=11Round 1, 1 → 3: 6 + 5 = 11 is better, so dist[3] = 11.
6L7round=1 u=1 v=4 dist[v]=2Round 1, 1 → 4: 6 + -4 = 2 is better, so dist[4] = 2.
7L7round=1 u=2 v=3 dist[v]=4Round 1, 2 → 3: 7 + -3 = 4 is better, so dist[3] = 4.
8L7round=1 edge=2 → 4 candidate=16Round 1, 2 → 4: 7 + 9 = 16 is not better than 2: no change.
9L7round=1 u=3 v=1 dist[v]=2Round 1, 3 → 1: 4 + -2 = 2 is better, so dist[1] = 2.
10L7round=1 edge=4 → 3 candidate=9Round 1, 4 → 3: 2 + 7 = 9 is not better than 4: no change.
11L9round=1 dist=[0, 2, 7, 4, 2]End of round 1: distances [0, 2, 7, 4, 2]. Paths with up to 1 edges are now correct.
12L7round=2 edge=0 → 1 candidate=6Round 2, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
13L7round=2 edge=0 → 2 candidate=7Round 2, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
14L7round=2 edge=1 → 2 candidate=10Round 2, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
15L7round=2 edge=1 → 3 candidate=7Round 2, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
16L7round=2 u=1 v=4 dist[v]=-2Round 2, 1 → 4: 2 + -4 = -2 is better, so dist[4] = -2.
17L7round=2 edge=2 → 3 candidate=4Round 2, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
18L7round=2 edge=2 → 4 candidate=16Round 2, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
19L7round=2 edge=3 → 1 candidate=2Round 2, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
20L7round=2 edge=4 → 3 candidate=5Round 2, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
21L9round=2 dist=[0, 2, 7, 4, -2]End of round 2: distances [0, 2, 7, 4, -2]. Paths with up to 2 edges are now correct.
22L7round=3 edge=0 → 1 candidate=6Round 3, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
23L7round=3 edge=0 → 2 candidate=7Round 3, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
24L7round=3 edge=1 → 2 candidate=10Round 3, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
25L7round=3 edge=1 → 3 candidate=7Round 3, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
26L7round=3 edge=1 → 4 candidate=-2Round 3, 1 → 4: 2 + -4 = -2 is not better than -2: no change.
27L7round=3 edge=2 → 3 candidate=4Round 3, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
28L7round=3 edge=2 → 4 candidate=16Round 3, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
29L7round=3 edge=3 → 1 candidate=2Round 3, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
30L7round=3 edge=4 → 3 candidate=5Round 3, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
31L9round=3Round 3 changed nothing, so no later round can: stop early.
32L12return=[0, 2, 7, 4, -2] relaxations=7No edge improves in the check pass: no negative cycle is reachable. Distances: [0, 2, 7, 4, -2]. Cost O(n · m).

Practice ladder

Now try it yourself

Easy

  • Network Delay Time

Medium

  • Cheapest Flights Within K Stops
  • Find the City With the Smallest Number of Neighbors at a Threshold Distance

Advanced

  • Minimum Cost to Reach Destination in Time
  • Number of Ways to Arrive at Destination

Key takeaways

  • Bellman-Ford relaxes every edge, n - 1 times; time O(n · m); it handles negative edges.
  • After k passes every shortest path of at most k edges is correct; stop early when a pass changes nothing.
  • An improvement in pass n proves a negative cycle reachable from the source; step back along the improving edges to extract it.
  • Vertices reachable from such a cycle have distance minus infinity; the others are unaffected.