35.01Intermediate / Advanced5 topics17 min5 interactive animations

Shortest path framework

The ideas shared by every shortest-path algorithm: distance estimates that only ever decrease through relaxation, parent links that record the path, the single-source and all-pairs problems, and what negative edges and negative cycles do to them.

Learning goals

Define relaxation and explain why it never makes an estimate wrong
Rebuild a path from parent links
Distinguish the single-source and all-pairs problems
Explain how negative edges and negative cycles change the problem

Prerequisites

Graph representationsBreadth-first search

Dijkstra, Bellman-Ford, Floyd-Warshall and A* look different, but all keep a table of the best distance found so far and improve it by one small operation. Seeing that operation first makes each algorithm a choice about the order in which to apply it.

35.01.1

Relaxation

Keep an estimate dist[v] for every vertex: the cost of the cheapest path found so far, starting at 0 for the source and infinity elsewhere. **Relaxing** an edge u → v of weight w asks whether going through u is cheaper: if dist[u] + w < dist[v], set dist[v] = dist[u] + w and remember parent[v] = u.

An estimate is always the cost of a real path, so it can only be too high, never too low, and relaxation only lowers it. The algorithms differ only in which edges they relax and in what order. Step through the animation to see each relaxation as an improvement or a no-change.

Java

1static boolean relax(long[] dist, int[] parent, int u, int v, long w) {   // can the route through u improve v?
2    if (dist[u] == Long.MAX_VALUE / 2) return false;                      // u has no route yet
3    if (dist[u] + w >= dist[v]) return false;
4    dist[v] = dist[u] + w;
5    parent[v] = u;
6    return true;
7}

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

Interactive · edit the input

directed graph · 5 vertices · 9 edges

d=0

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

dist[v]

∞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

No condition evaluated on this step

Execution trace (dry run table)Show 32 steps

Step	Line	State	What happens
1	L3	source=0	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.
2	L7	round=1 u=0 v=1 dist[v]=6	Round 1, 0 → 1: 0 + 6 = 6 is better, so dist[1] = 6.
3	L7	round=1 u=0 v=2 dist[v]=7	Round 1, 0 → 2: 0 + 7 = 7 is better, so dist[2] = 7.
4	L7	round=1 edge=1 → 2 candidate=14	Round 1, 1 → 2: 6 + 8 = 14 is not better than 7: no change.
5	L7	round=1 u=1 v=3 dist[v]=11	Round 1, 1 → 3: 6 + 5 = 11 is better, so dist[3] = 11.
6	L7	round=1 u=1 v=4 dist[v]=2	Round 1, 1 → 4: 6 + -4 = 2 is better, so dist[4] = 2.
7	L7	round=1 u=2 v=3 dist[v]=4	Round 1, 2 → 3: 7 + -3 = 4 is better, so dist[3] = 4.
8	L7	round=1 edge=2 → 4 candidate=16	Round 1, 2 → 4: 7 + 9 = 16 is not better than 2: no change.
9	L7	round=1 u=3 v=1 dist[v]=2	Round 1, 3 → 1: 4 + -2 = 2 is better, so dist[1] = 2.
10	L7	round=1 edge=4 → 3 candidate=9	Round 1, 4 → 3: 2 + 7 = 9 is not better than 4: no change.
11	L9	round=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.
12	L7	round=2 edge=0 → 1 candidate=6	Round 2, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
13	L7	round=2 edge=0 → 2 candidate=7	Round 2, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
14	L7	round=2 edge=1 → 2 candidate=10	Round 2, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
15	L7	round=2 edge=1 → 3 candidate=7	Round 2, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
16	L7	round=2 u=1 v=4 dist[v]=-2	Round 2, 1 → 4: 2 + -4 = -2 is better, so dist[4] = -2.
17	L7	round=2 edge=2 → 3 candidate=4	Round 2, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
18	L7	round=2 edge=2 → 4 candidate=16	Round 2, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
19	L7	round=2 edge=3 → 1 candidate=2	Round 2, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
20	L7	round=2 edge=4 → 3 candidate=5	Round 2, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
21	L9	round=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.
22	L7	round=3 edge=0 → 1 candidate=6	Round 3, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
23	L7	round=3 edge=0 → 2 candidate=7	Round 3, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
24	L7	round=3 edge=1 → 2 candidate=10	Round 3, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
25	L7	round=3 edge=1 → 3 candidate=7	Round 3, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
26	L7	round=3 edge=1 → 4 candidate=-2	Round 3, 1 → 4: 2 + -4 = -2 is not better than -2: no change.
27	L7	round=3 edge=2 → 3 candidate=4	Round 3, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
28	L7	round=3 edge=2 → 4 candidate=16	Round 3, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
29	L7	round=3 edge=3 → 1 candidate=2	Round 3, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
30	L7	round=3 edge=4 → 3 candidate=5	Round 3, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
31	L9	round=3	Round 3 changed nothing, so no later round can: stop early.
32	L12	return=[0, 2, 7, 4, -2] relaxations=7	No edge improves in the check pass: no negative cycle is reachable. Distances: [0, 2, 7, 4, -2]. Cost O(n · m).

35.01.2

Parent reconstruction

The distance table alone does not say *which* path is shortest. Store parent[v], the vertex that last improved v. Starting at the target and following parents back to the source (where parent is -1) gives the path in reverse; reverse it for the answer.

The parent links of all reachable vertices form a tree rooted at the source, the **shortest-path tree**. Storing one parent per vertex takes O(n) memory instead of storing a whole path for each vertex. The Dijkstra animation highlights the tree and the final path.

Java

1static List<Integer> pathFromParents(int[] parent, long[] dist, int s, int t) {   // parent[s] == -1; empty when t is unreachable
2    List<Integer> path = new ArrayList<>();
3    if (dist[t] >= Long.MAX_VALUE / 2) return path;
4    for (int v = t; v != -1; v = parent[v]) path.add(v);                          // walk back to the source
5    Collections.reverse(path);
6    return path;
7}

Dijkstra with a priority queue: lazy deletion and path reconstruction

Interactive · edit the input

undirected graph · 6 vertices · 9 edges

d=0

Being settledHas a queue entrySettledTree edge / on the pathOutdated entry skipped

queue {dist, vertex}, smallest first

0,0

dist[v]

∞1

∞2

∞3

∞4

∞5

Setup

Start with {0, 0} in the priority queue. The queue always gives the unsettled vertex with the smallest known distance; with non-negative weights nothing found later can beat it.

Step 1 / 28

Java

1long[] dijkstra(int n, List<int[]>[] adj, int s, int[] parent) {   // adj[u] = {v, w}, all w >= 0
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0;
4    Arrays.fill(parent, -1);
5    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));   // {distance, vertex}
6    pq.add(new long[]{0, s});
7    while (!pq.isEmpty()) {
8        long[] top = pq.poll(); int u = (int) top[1];
9        if (top[0] > dist[u]) continue;           // outdated entry: u was already improved
10        for (int[] e : adj[u]) {
11            if (dist[u] + e[1] >= dist[e[0]]) continue;
12            dist[e[0]] = dist[u] + e[1]; parent[e[0]] = u;
13            pq.add(new long[]{dist[e[0]], e[0]});   // lazy: the old entry stays in the queue
14        }
15    }
16    return dist;
17}
18List<Integer> pathTo(int[] parent, int t) {       // follow parents back from t
19    LinkedList<Integer> p = new LinkedList<>();
20    for (int v = t; v != -1; v = parent[v]) p.addFirst(v);
21    return p;
22}

Live state

1 entries pushed0 outdated entries skipped

source

No condition evaluated on this step

Execution trace (dry run table)Show 28 steps

Step	Line	State	What happens
1	L6	source=0	Start with {0, 0} in the priority queue. The queue always gives the unsettled vertex with the smallest known distance; with non-negative weights nothing found later can beat it.
2	L8	u=0 dist[u]=0	Pop {0, 0}: the distance to 0 is final (0). Relax its edges.
3	L12	u=0 v=1 dist[v]=7	0 → 1: 0 + 7 = 7. dist[1] = 7, parent[1] = 0, and a new entry {7, 1} is pushed.
4	L12	u=0 v=2 dist[v]=9	0 → 2: 0 + 9 = 9. dist[2] = 9, parent[2] = 0, and a new entry {9, 2} is pushed.
5	L12	u=0 v=5 dist[v]=14	0 → 5: 0 + 14 = 14. dist[5] = 14, parent[5] = 0, and a new entry {14, 5} is pushed.
6	L8	u=1 dist[u]=7	Pop {7, 1}: the distance to 1 is final (7). Relax its edges.
7	L10	u=1 v=0 candidate=14	1 → 0: 7 + 7 = 14 does not beat 0.
8	L10	u=1 v=2 candidate=17	1 → 2: 7 + 10 = 17 does not beat 9.
9	L12	u=1 v=3 dist[v]=22	1 → 3: 7 + 15 = 22. dist[3] = 22, parent[3] = 1, and a new entry {22, 3} is pushed.
10	L8	u=2 dist[u]=9	Pop {9, 2}: the distance to 2 is final (9). Relax its edges.
11	L10	u=2 v=0 candidate=18	2 → 0: 9 + 9 = 18 does not beat 0.
12	L10	u=2 v=1 candidate=19	2 → 1: 9 + 10 = 19 does not beat 7.
13	L12	u=2 v=3 dist[v]=20	2 → 3: 9 + 11 = 20. dist[3] = 20, parent[3] = 2, and a new entry {20, 3} is pushed; the older, larger entry for 3 stays in the queue.
14	L12	u=2 v=5 dist[v]=11	2 → 5: 9 + 2 = 11. dist[5] = 11, parent[5] = 2, and a new entry {11, 5} is pushed; the older, larger entry for 5 stays in the queue.
15	L8	u=5 dist[u]=11	Pop {11, 5}: the distance to 5 is final (11). Relax its edges.
16	L10	u=5 v=0 candidate=25	5 → 0: 11 + 14 = 25 does not beat 0.
17	L10	u=5 v=2 candidate=13	5 → 2: 11 + 2 = 13 does not beat 9.
18	L12	u=5 v=4 dist[v]=20	5 → 4: 11 + 9 = 20. dist[4] = 20, parent[4] = 5, and a new entry {20, 4} is pushed.
19	L9	entry=14,5 dist[v]=11	Pop {14, 5}, but dist[5] is already 11: this entry is outdated (a shorter route was found after it was pushed). Skip it. Skipping instead of deleting is called lazy deletion.
20	L8	u=3 dist[u]=20	Pop {20, 3}: the distance to 3 is final (20). Relax its edges.
21	L10	u=3 v=1 candidate=35	3 → 1: 20 + 15 = 35 does not beat 7.
22	L10	u=3 v=2 candidate=31	3 → 2: 20 + 11 = 31 does not beat 9.
23	L10	u=3 v=4 candidate=26	3 → 4: 20 + 6 = 26 does not beat 20.
24	L8	u=4 dist[u]=20	Pop {20, 4}: the distance to 4 is final (20). Relax its edges.
25	L10	u=4 v=3 candidate=26	4 → 3: 20 + 6 = 26 does not beat 20.
26	L10	u=4 v=5 candidate=29	4 → 5: 20 + 9 = 29 does not beat 11.
27	L9	entry=22,3 dist[v]=20	Pop {22, 3}, but dist[3] is already 20: this entry is outdated (a shorter route was found after it was pushed). Skip it. Skipping instead of deleting is called lazy deletion.
28	L15	return=[0, 7, 9, 20, 20, 11] pushed=8 skipped=2	Distances: [0, 7, 9, 20, 20, 11] (∞ = unreachable). 8 entries pushed, 2 skipped as outdated; each arrow pushes at most one entry (an undirected edge is two arrows), so the cost is O(m log m). Following parents back from 4 gives the path 0 → 2 → 5 → 4 with total weight 20.

35.01.3

Single-source vs all-pairs

The **single-source** problem asks for the distance from one vertex to every other; the **single-pair** problem asks for one distance and can stop early; the **all-pairs** problem asks for the distance between every ordered pair. A single-source algorithm run from each vertex solves all-pairs, but a dedicated algorithm may be better.

Which method fits depends on the weights and the density of the graph. The table lists the standard choices, each covered in this chapter. Floyd-Warshall, in the animation, solves all-pairs directly with three loops.

Situation	Algorithm	Time
Unweighted	BFS	O(n + m)
Weights 0 and 1	0-1 BFS	O(n + m)
Non-negative weights	Dijkstra with a heap	O((n + m) log n)
Negative weights, no negative cycle	Bellman-Ford	O(n · m)
DAG, any weights	Relax in topological order	O(n + m)
All pairs, dense or small n	Floyd-Warshall	O(n³)
All pairs, sparse, negative edges	Johnson	O(n · m log n)

Java

1static long[][] allPairsByBellmanFord(int n, int[][] edges) {   // n single-source runs; null on a negative cycle
2    long INF = Long.MAX_VALUE / 2;
3    long[][] d = new long[n][n];
4    for (int s = 0; s < n; s++) {
5        Arrays.fill(d[s], INF);
6        d[s][s] = 0;
7        for (int round = 0; round < n; round++) {
8            boolean changed = false;
9            for (int[] e : edges)
10                if (d[s][e[0]] != INF && d[s][e[0]] + e[2] < d[s][e[1]]) { d[s][e[1]] = d[s][e[0]] + e[2]; changed = true; }
11            if (!changed) break;
12            if (round == n - 1) return null;                    // still improving after n rounds
13        }
14    }
15    return d;
16}

Floyd-Warshall: all-pairs shortest paths and transitive closure

Interactive · edit the input

grid · 5 × 5

01234

∞

-2

∞

Cell just improvedRow k and column k (the new intermediate vertex)Known value

Setup

d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.

Step 1 / 11

Java

1long[][] floydWarshall(int n, int[][] edges) {    // edges: {u, v, w}; null when a negative cycle exists
2    long INF = Long.MAX_VALUE / 4;
3    long[][] d = new long[n][n];
4    for (long[] r : d) Arrays.fill(r, INF);
5    for (int i = 0; i < n; i++) d[i][i] = 0;
6    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);   // keep the lightest parallel edge
7    for (int k = 0; k < n; k++)                   // intermediate vertices allowed so far: 0..k
8        for (int i = 0; i < n; i++)
9            for (int j = 0; j < n; j++)
10                if (d[i][k] < INF && d[k][j] < INF && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
11    for (int i = 0; i < n; i++) if (d[i][i] < 0) return null;   // a vertex that returns to itself with negative cost
12    return d;
13}

Live state

0 improvements

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3	n=4	d[i][j] is the cheapest known cost from i to j using no intermediate vertices: the arrow weight (lightest if parallel), 0 on the diagonal, ∞ otherwise. Each round k allows vertex k as an intermediate stop.
2	L7	k=0	Round 0: going through 0 changes nothing.
3	L9	k=1 i=0 j=2 d[i][j]=1	Through 1: d[0][1] + d[1][2] = 3 + -2 = 1, better than the old d[0][2]. Update it.
4	L9	k=1 i=3 j=2 d[i][j]=-1	Through 1: d[3][1] + d[1][2] = 1 + -2 = -1, better than the old d[3][2]. Update it.
5	L7	k=1	Round 1 done: some distances improved by going through 1. Intermediate vertices 0..1 are now allowed.
6	L9	k=2 i=0 j=3 d[i][j]=3	Through 2: d[0][2] + d[2][3] = 1 + 2 = 3, better than the old d[0][3]. Update it.
7	L9	k=2 i=1 j=3 d[i][j]=0	Through 2: d[1][2] + d[2][3] = -2 + 2 = 0, better than the old d[1][3]. Update it.
8	L7	k=2	Round 2 done: some distances improved by going through 2. Intermediate vertices 0..2 are now allowed.
9	L9	k=3 i=2 j=1 d[i][j]=3	Through 3: d[2][3] + d[3][1] = 2 + 1 = 3, better than the old d[2][1]. Update it.
10	L7	k=3	Round 3 done: some distances improved by going through 3. Intermediate vertices 0..3 are now allowed.
11	L12	return=[0, 3, 1, 3] \| [-, 0, -2, 0] \| [-, 3, 0, 2] \| [-, 1, -1, 0] improvements=5	The diagonal is all zeros, so there is no negative cycle. Row i holds the shortest distance from i to every vertex ('∞' = unreachable). Three nested loops: O(n³) time, O(n²) space.

35.01.4

Negative edges

A negative edge is allowed in many applications (a refund, a discount, an energy gain). Dijkstra's reasoning breaks: it treats the closest unsettled vertex as final because any other route must add non-negative cost, which is false when a later edge can subtract.

Open the old Dijkstra animation on its negative-edge preset: the vertex settled first keeps a distance that a longer route with a negative edge would have beaten. Bellman-Ford or DAG ordering handle negative edges correctly. The code below is the settle-once algorithm; it is exactly right for non-negative weights and wrong otherwise.

Java

1static long[] dijkstraSettleOnce(int n, int[][] edges, int s) {   // correct only when every weight >= 0
2    long INF = Long.MAX_VALUE / 2;
3    long[] dist = new long[n];
4    Arrays.fill(dist, INF);
5    dist[s] = 0;
6    boolean[] done = new boolean[n];
7    for (int step = 0; step < n; step++) {
8        int u = -1;
9        for (int v = 0; v < n; v++) if (!done[v] && dist[v] < INF && (u == -1 || dist[v] < dist[u])) u = v;
10        if (u == -1) break;
11        done[u] = true;                                          // trusted as final: false when a negative edge can still lower it
12        for (int[] e : edges)
13            if (e[0] == u && !done[e[1]] && dist[u] + e[2] < dist[e[1]]) dist[e[1]] = dist[u] + e[2];
14    }
15    return dist;
16}

Dijkstra's shortest paths, and why negative edges break it

Interactive · edit the input

dist[] from vertex 0

0v0

∞v1

∞v2

∞v3

Setup

Distances start at ∞ except the source. Each step settles the closest unsettled vertex and relaxes its outgoing edges. Its distance is declared final, which is only justified when no edge is negative.

Step 1 / 11

Java

1static int[] dijkstra(int n, List<int[]>[] adj, int src) {  // adj[u] = list of {v, weight}
2    int[] dist = new int[n]; Arrays.fill(dist, INF); dist[src] = 0;
3    boolean[] done = new boolean[n];
4    for (int step = 0; step < n; step++) {
5        int u = -1;
6        for (int v = 0; v < n; v++) if (!done[v] && dist[v] < INF && (u == -1 || dist[v] < dist[u])) u = v;   // closest unsettled vertex
7        if (u == -1) break;
8        done[u] = true;                                       // final: valid only when no edge is negative
9        for (int[] e : adj[u]) if (!done[e[0]] && dist[u] + e[1] < dist[e[0]]) dist[e[0]] = dist[u] + e[1];   // relax
10    }
11    return dist;
12}

Live state

vertices

negative

false

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L2	vertices=4 negative=false	Distances start at ∞ except the source. Each step settles the closest unsettled vertex and relaxes its outgoing edges. Its distance is declared final, which is only justified when no edge is negative.
2	L8	settled=0 dist=0	Settle vertex 0 with distance 0: from now on it will not be updated.
3	L9	edge=0>1:4 new dist=4	Relax 0>1: 0 + 4 = 4 beats the old distance.
4	L9	edge=0>2:1 new dist=1	Relax 0>2: 0 + 1 = 1 beats the old distance.
5	L8	settled=2 dist=1	Settle vertex 2 with distance 1: from now on it will not be updated.
6	L9	edge=2>1:2 new dist=3	Relax 2>1: 1 + 2 = 3 beats the old distance.
7	L9	edge=2>3:5 new dist=6	Relax 2>3: 1 + 5 = 6 beats the old distance.
8	L8	settled=1 dist=3	Settle vertex 1 with distance 3: from now on it will not be updated.
9	L9	edge=1>3:1 new dist=4	Relax 1>3: 3 + 1 = 4 beats the old distance.
10	L8	settled=3 dist=4	Settle vertex 3 with distance 4: from now on it will not be updated.
11	L11	return=[0, 3, 1, 4] reference=[0, 3, 1, 4]	Distances [0, 3, 1, 4] match the Bellman-Ford reference.

35.01.5

Negative cycles

A **negative cycle** is a cycle whose edge weights add up to less than zero. Going round it again lowers the cost, so a path that can reach the cycle and then go on to the target has no minimum: the distance is -infinity. Shortest paths are only defined when no negative cycle is reachable from the source.

An undirected edge with negative weight is itself a negative cycle (walk back and forth). Algorithms must detect the situation rather than loop forever: Bellman-Ford does so with one extra pass. Choose the negative-cycle presets in the Bellman-Ford animation. The code below checks the whole graph, starting from every vertex at once.

Java

1static boolean hasNegativeCycle(int n, int[][] edges) {          // anywhere in the graph, reachable from a given source or not
2    long[] dist = new long[n];                                    // all start at 0: as if a virtual source reached every vertex for free
3    for (int round = 0; round < n; round++) {
4        boolean changed = false;
5        for (int[] e : edges)
6            if (dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
7        if (!changed) return false;
8    }
9    return true;                                                  // still improving after n rounds
10}

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

Interactive · edit the input

directed graph · 5 vertices · 9 edges

d=0

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

dist[v]

∞1

∞2

∞3

∞4

Setup

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

No condition evaluated on this step

Execution trace (dry run table)Show 32 steps

Step	Line	State	What happens
1	L3	source=0	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.
2	L7	round=1 u=0 v=1 dist[v]=6	Round 1, 0 → 1: 0 + 6 = 6 is better, so dist[1] = 6.
3	L7	round=1 u=0 v=2 dist[v]=7	Round 1, 0 → 2: 0 + 7 = 7 is better, so dist[2] = 7.
4	L7	round=1 edge=1 → 2 candidate=14	Round 1, 1 → 2: 6 + 8 = 14 is not better than 7: no change.
5	L7	round=1 u=1 v=3 dist[v]=11	Round 1, 1 → 3: 6 + 5 = 11 is better, so dist[3] = 11.
6	L7	round=1 u=1 v=4 dist[v]=2	Round 1, 1 → 4: 6 + -4 = 2 is better, so dist[4] = 2.
7	L7	round=1 u=2 v=3 dist[v]=4	Round 1, 2 → 3: 7 + -3 = 4 is better, so dist[3] = 4.
8	L7	round=1 edge=2 → 4 candidate=16	Round 1, 2 → 4: 7 + 9 = 16 is not better than 2: no change.
9	L7	round=1 u=3 v=1 dist[v]=2	Round 1, 3 → 1: 4 + -2 = 2 is better, so dist[1] = 2.
10	L7	round=1 edge=4 → 3 candidate=9	Round 1, 4 → 3: 2 + 7 = 9 is not better than 4: no change.
11	L9	round=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.
12	L7	round=2 edge=0 → 1 candidate=6	Round 2, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
13	L7	round=2 edge=0 → 2 candidate=7	Round 2, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
14	L7	round=2 edge=1 → 2 candidate=10	Round 2, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
15	L7	round=2 edge=1 → 3 candidate=7	Round 2, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
16	L7	round=2 u=1 v=4 dist[v]=-2	Round 2, 1 → 4: 2 + -4 = -2 is better, so dist[4] = -2.
17	L7	round=2 edge=2 → 3 candidate=4	Round 2, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
18	L7	round=2 edge=2 → 4 candidate=16	Round 2, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
19	L7	round=2 edge=3 → 1 candidate=2	Round 2, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
20	L7	round=2 edge=4 → 3 candidate=5	Round 2, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
21	L9	round=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.
22	L7	round=3 edge=0 → 1 candidate=6	Round 3, 0 → 1: 0 + 6 = 6 is not better than 2: no change.
23	L7	round=3 edge=0 → 2 candidate=7	Round 3, 0 → 2: 0 + 7 = 7 is not better than 7: no change.
24	L7	round=3 edge=1 → 2 candidate=10	Round 3, 1 → 2: 2 + 8 = 10 is not better than 7: no change.
25	L7	round=3 edge=1 → 3 candidate=7	Round 3, 1 → 3: 2 + 5 = 7 is not better than 4: no change.
26	L7	round=3 edge=1 → 4 candidate=-2	Round 3, 1 → 4: 2 + -4 = -2 is not better than -2: no change.
27	L7	round=3 edge=2 → 3 candidate=4	Round 3, 2 → 3: 7 + -3 = 4 is not better than 4: no change.
28	L7	round=3 edge=2 → 4 candidate=16	Round 3, 2 → 4: 7 + 9 = 16 is not better than -2: no change.
29	L7	round=3 edge=3 → 1 candidate=2	Round 3, 3 → 1: 4 + -2 = 2 is not better than 2: no change.
30	L7	round=3 edge=4 → 3 candidate=5	Round 3, 4 → 3: -2 + 7 = 5 is not better than 4: no change.
31	L9	round=3	Round 3 changed nothing, so no later round can: stop early.
32	L12	return=[0, 2, 7, 4, -2] relaxations=7	No 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

Find if Path Exists in Graph
Network Delay Time

Medium

Cheapest Flights Within K Stops
Path with Maximum Probability
Path With Minimum Effort

Advanced

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

Key takeaways

Every shortest-path algorithm repeats one step, relaxation: if dist[u] + w < dist[v], lower dist[v].
Parent links form the shortest-path tree; follow them back from the target to read a path.
Single-source, single-pair and all-pairs problems call for different algorithms; choose by weights and density.
Negative edges break settle-once Dijkstra; a reachable negative cycle makes distances undefined.