In the previous chapter, we learned that Dijkstra's algorithm is fast, but it has one big weakness: it does not work with negative edge weights.
Negative weights are not just a textbook trick. They appear in real problems:
A delivery route where some stops give you a cashback instead of costing money.
Currency exchange, where a sequence of trades might gain value.
Energy in a game, where some tiles restore energy.
There is also a second question Dijkstra does not directly answer: what if we want the shortest distance between every pair of vertices, not just from one source?
This chapter covers two classic algorithms for these situations:
Bellman-Ford → single source, negative edges allowed, detects negative cycles
Floyd-Warshall → all pairs, negative edges allowed, detects negative cyclesNegative Edges and Negative Cycles
Before learning the algorithms, we must understand the difference between a negative edge and a negative cycle.
A negative cycle is a cycle whose total edge weight is less than zero.
Example:
1 → 2 : -1
2 → 3 : -1
3 → 1 : -1
Cycle 1 → 2 → 3 → 1 has total weight -3If a negative cycle is reachable, we can go around it again and again, and the path cost keeps dropping forever:
Once around → -3
Twice around → -6
Three times → -9
...So the "shortest path" does not exist. It would be -∞.
That gives us an important rule:
Situation | Shortest paths well defined? |
|---|---|
All weights non-negative | Yes (Dijkstra works) |
Some negative edges, but no negative cycle | Yes (use Bellman-Ford or Floyd-Warshall) |
A reachable negative cycle | No, but the algorithms can detect it |
Part 1: Bellman-Ford Algorithm
The Bellman-Ford algorithm finds single-source shortest paths in a weighted directed graph that may contain negative edges, and it can detect whether a negative cycle is reachable from the source.
It uses the same relaxation step we saw in Dijkstra:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wThe difference is how it chooses which edges to relax.
Dijkstra: greedily picks the closest vertex and relaxes its edges once
Bellman-Ford: relaxes EVERY edge, again and again, V - 1 timesBellman-Ford does not need a priority queue. It is simpler, but slower.
Why V - 1 Passes?
If there is no negative cycle, a shortest path never needs to repeat a vertex. A path that visits each vertex at most once in a graph with V vertices has at most V - 1 edges.
After each full pass over all edges, at least one more edge of every shortest path becomes correct:
After pass 1 → all shortest paths using 1 edge are correct
After pass 2 → all shortest paths using up to 2 edges are correct
...
After pass V-1 → all shortest paths (up to V-1 edges) are correctSo V - 1 passes are always enough.
Bellman-Ford Step by Step
Consider this directed graph with 4 vertices and source 0:
4 -3 2
0 ──────→ 1 ──────→ 2 ──────→ 3
│ ↑
└───────────────────┘
5We store the graph as a simple edge list, in this order:
(2 → 3, 2)
(1 → 2, -3)
(0 → 1, 4)
(0 → 2, 5)Start:
dist = [0, ∞, ∞, ∞]Pass 1
2 → 3 : dist[2] is ∞, skip
1 → 2 : dist[1] is ∞, skip
0 → 1 : 0 + 4 = 4 < ∞ → dist[1] = 4
0 → 2 : 0 + 5 = 5 < ∞ → dist[2] = 5
dist = [0, 4, 5, ∞]Pass 2
2 → 3 : 5 + 2 = 7 < ∞ → dist[3] = 7
1 → 2 : 4 - 3 = 1 < 5 → dist[2] = 1
0 → 1 : 0 + 4 = 4, no change
0 → 2 : 0 + 5 = 5, no change
dist = [0, 4, 1, 7]Pass 3
2 → 3 : 1 + 2 = 3 < 7 → dist[3] = 3
(other edges: no change)
dist = [0, 4, 1, 3]We have done V - 1 = 3 passes, so we are finished:
dist = [0, 4, 1, 3]Notice how the edge order affected the work. Because 2 → 3 was checked first, it needed three passes for the improvement to travel along 0 → 1 → 2 → 3. With a luckier order, fewer passes would have been enough, but V - 1 passes guarantee the right answer for any order.
Detecting a Negative Cycle
After V - 1 passes, every shortest path is already final, if no negative cycle exists.
So we do one extra pass:
for each edge (u → v, w):
if dist[u] + w < dist[v]:
negative cycle exists!If any distance can still improve, the only explanation is a reachable negative cycle.
Bellman-Ford in Java
This program runs Bellman-Ford on the example above, and then on a graph containing the negative cycle 1 → 2 → 3 → 1. It prints dist[] after every pass so you can match it with the trace.
import java.util.Arrays;
class Main {
static final int INF = Integer.MAX_VALUE;
// Returns null if a negative cycle is reachable from the source
static int[] bellmanFord(int n, int[][] edges, int source) {
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[source] = 0;
// Relax every edge, V - 1 times
for (int i = 1; i <= n - 1; i++) {
boolean changed = false;
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
changed = true;
}
}
System.out.println("After pass " + i + ": " + show(dist));
if (!changed) {
break; // nothing improved, we are done early
}
}
// One more pass: any improvement means a negative cycle
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != INF && dist[u] + w < dist[v]) {
return null;
}
}
return dist;
}
static String show(int[] dist) {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < dist.length; i++) {
if (i > 0) {
sb.append(", ");
}
sb.append(dist[i] == INF ? "INF" : String.valueOf(dist[i]));
}
return sb.append("]").toString();
}
public static void main(String[] args) {
// {from, to, weight}
int[][] edges = {
{2, 3, 2},
{1, 2, -3},
{0, 1, 4},
{0, 2, 5}
};
int[] dist = bellmanFord(4, edges, 0);
System.out.println("Shortest distances: " + show(dist));
System.out.println();
int[][] cyclic = {
{0, 1, 1},
{1, 2, -1},
{2, 3, -1},
{3, 1, -1}
};
int[] result = bellmanFord(4, cyclic, 0);
if (result == null) {
System.out.println("Negative cycle detected!");
}
}
}Output:
After pass 1: [0, 4, 5, INF]
After pass 2: [0, 4, 1, 7]
After pass 3: [0, 4, 1, 3]
Shortest distances: [0, 4, 1, 3]
After pass 1: [0, -2, 0, -1]
After pass 2: [0, -5, -3, -4]
After pass 3: [0, -8, -6, -7]
Negative cycle detected!In the second graph, the distances keep falling by 3 every pass (the weight of the cycle). They would never settle, which is exactly what the extra pass detects.
Important Details in the Code
The dist[u] != INF Check
if (dist[u] != INF && dist[u] + w < dist[v])This check is essential. If dist[u] is Integer.MAX_VALUE and w is positive, dist[u] + w overflows into a negative number, and the comparison would wrongly succeed. Also, a vertex we have not reached yet should not be used to relax anything.
Early Exit
if (!changed) {
break;
}If a full pass changes nothing, no later pass can change anything either, so we can stop. This does not improve the worst case, but in practice it often saves a lot of time. It also does not break the negative cycle check: if nothing changed, a negative cycle cannot be reachable.
Why an Edge List?
Bellman-Ford simply loops over all edges, so an edge list ({from, to, weight}) is the most natural representation. An adjacency list also works: loop over every vertex and then over its edges.
Bellman-Ford Complexity
We do up to V - 1 passes (plus one check pass), and each pass looks at all E edges.
Time → O(V · E)
Space → O(V) (for dist[], not counting the edge list)Compare with Dijkstra:
Dijkstra → O((V + E) log V) faster, but no negative edges
Bellman-Ford → O(V · E) slower, but handles negative edgesBellman-Ford and Undirected Graphs
Be careful with undirected graphs. An undirected edge u - v with weight -2 is really two directed edges:
u → v : -2
v → u : -2Together they form the cycle u → v → u with weight -4, which is a negative cycle. So any negative edge in an undirected graph creates a negative cycle, and shortest paths are not defined.
Part 2: Floyd-Warshall Algorithm
Sometimes we need the shortest distance between every pair of vertices. For example, a table of shortest road distances between all cities in a state.
We could run Bellman-Ford (or Dijkstra) once from every vertex. But there is a beautifully short algorithm designed for exactly this job.
The Floyd-Warshall algorithm finds the shortest distances between all pairs of vertices in a weighted graph. It allows negative edges, as long as there is no negative cycle.
The Key Idea: Intermediate Vertices
Floyd-Warshall keeps a 2D matrix:
dist[i][j] = shortest known distance from i to jIt starts with only direct edges:
dist[i][i] = 0
dist[i][j] = weight of edge i → j, if it exists
dist[i][j] = ∞, otherwiseThen it asks one question for every vertex k, one at a time:
Would going from i to j through k be shorter than the best path found so far?
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )Picture it like this:
dist[i][k] dist[k][j]
i ──────────────→ k ──────────────→ j
i ─────────────────────────────────→ j
dist[i][j]After we finish with k = 0, dist[i][j] is the shortest path that may use vertex 0 in the middle. After k = 1, it may use vertices 0 and 1. After the last k, it may use any vertex, so it is the true shortest distance.
This idea of building the answer from smaller, already-solved subproblems is called dynamic programming. We will study it properly in a later chapter; for now, just remember the rule above.
Floyd-Warshall Step by Step
Consider this directed graph:
0 → 1 : 3
0 → 3 : 7
1 → 0 : 8
1 → 2 : 2
2 → 0 : 5
2 → 3 : 1
3 → 0 : 2Initial matrix:
0 1 2 3
0 0 3 ∞ 7
1 8 0 2 ∞
2 5 ∞ 0 1
3 2 ∞ ∞ 0k = 0 (allow paths through vertex 0)
1 → 0 → 3 : 8 + 7 = 15 < ∞ → dist[1][3] = 15
2 → 0 → 1 : 5 + 3 = 8 < ∞ → dist[2][1] = 8
3 → 0 → 1 : 2 + 3 = 5 < ∞ → dist[3][1] = 5
0 1 2 3
0 0 3 ∞ 7
1 8 0 2 15
2 5 8 0 1
3 2 5 ∞ 0k = 1 (allow vertices 0 and 1)
0 → 1 → 2 : 3 + 2 = 5 < ∞ → dist[0][2] = 5
3 → 1 → 2 : 5 + 2 = 7 < ∞ → dist[3][2] = 7
0 1 2 3
0 0 3 5 7
1 8 0 2 15
2 5 8 0 1
3 2 5 7 0k = 2 (allow vertices 0, 1 and 2)
0 → 2 → 3 : 5 + 1 = 6 < 7 → dist[0][3] = 6
1 → 2 → 0 : 2 + 5 = 7 < 8 → dist[1][0] = 7
1 → 2 → 3 : 2 + 1 = 3 < 15 → dist[1][3] = 3
0 1 2 3
0 0 3 5 6
1 7 0 2 3
2 5 8 0 1
3 2 5 7 0k = 3 (allow all vertices)
1 → 3 → 0 : 3 + 2 = 5 < 7 → dist[1][0] = 5
2 → 3 → 0 : 1 + 2 = 3 < 5 → dist[2][0] = 3
2 → 3 → 1 : 1 + 5 = 6 < 8 → dist[2][1] = 6
0 1 2 3
0 0 3 5 6
1 5 0 2 3
2 3 6 0 1
3 2 5 7 0This final matrix gives the shortest distance between every pair. For example, the shortest path from 1 to 0 is 1 → 2 → 3 → 0 with cost 2 + 1 + 2 = 5.
Floyd-Warshall in Java
class Main {
static final int INF = 1_000_000_000; // "infinity" that is safe to add
static void floydWarshall(int[][] dist) {
int n = dist.length;
for (int k = 0; k < n; k++) { // intermediate vertex
for (int i = 0; i < n; i++) { // source
for (int j = 0; j < n; j++) { // destination
if (dist[i][k] != INF && dist[k][j] != INF
&& dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
static void print(int[][] dist) {
for (int[] row : dist) {
StringBuilder sb = new StringBuilder();
for (int x : row) {
sb.append(String.format("%5s", x == INF ? "INF" : String.valueOf(x)));
}
System.out.println(sb);
}
}
public static void main(String[] args) {
int[][] dist = {
{0, 3, INF, 7 },
{8, 0, 2, INF},
{5, INF, 0, 1 },
{2, INF, INF, 0 }
};
floydWarshall(dist);
print(dist);
boolean negativeCycle = false;
for (int i = 0; i < dist.length; i++) {
if (dist[i][i] < 0) {
negativeCycle = true;
}
}
System.out.println("Negative cycle: " + negativeCycle);
}
}Output:
0 3 5 6
5 0 2 3
3 6 0 1
2 5 7 0
Negative cycle: falseThe whole algorithm is just three nested loops. That is why Floyd-Warshall is a favorite in interviews and exams.
Important Details in Floyd-Warshall
The Loop Order Matters
k (the intermediate vertex) must be the outermost loop.
Correct: for k → for i → for j
Wrong: for i → for j → for kWhen we use k as the middle vertex, the values dist[i][k] and dist[k][j] must already include every shorter route through vertices 0 ... k-1. Putting k inside would compute dist[i][j] before those values are ready, and can give wrong answers.
Choosing INF Carefully
We used INF = 1_000_000_000 instead of Integer.MAX_VALUE. Even so, we still check dist[i][k] != INF && dist[k][j] != INF. This avoids overflow and also avoids treating "unreachable + negative edge" as a real path.
Detecting a Negative Cycle
The distance from a vertex to itself starts at 0. If, after the algorithm, any dist[i][i] becomes negative, then there is a way to leave i and come back with negative total cost: a negative cycle.
dist[i][i] < 0 → vertex i is on a negative cycleReconstructing Paths
To print the actual path, keep a next[i][j] matrix that stores the first vertex after i on the best path to j. Whenever dist[i][j] improves through k, set next[i][j] = next[i][k].
Floyd-Warshall Complexity
Three nested loops, each running V times:
Time → O(V³)
Space → O(V²) (the distance matrix)For V = 400, V³ = 64,000,000 simple operations, which is fine. For V = 10,000, it is 10¹², which is far too slow. So Floyd-Warshall is used only when the number of vertices is small (typically a few hundred).
Comparing All Shortest Path Algorithms
Algorithm | Problem | Negative edges | Negative cycle detection | Time |
|---|---|---|---|---|
BFS | Single source, unweighted | Not applicable | Not applicable | O(V + E) |
Dijkstra | Single source | No | No | O((V + E) log V) |
Bellman-Ford | Single source | Yes | Yes | O(V · E) |
Floyd-Warshall | All pairs | Yes | Yes (dist[i][i] < 0) | O(V³) |
A quick decision guide:
Unweighted graph? → BFS
Weighted, all weights ≥ 0, one source? → Dijkstra
Negative weights, one source? → Bellman-Ford
Need to detect a negative cycle? → Bellman-Ford (or Floyd-Warshall)
Need all pairs, V is small (≤ ~400)? → Floyd-Warshall
Need all pairs, weights ≥ 0, V is large? → Dijkstra from every vertexReal-Life Applications
Distance-vector routing: routing protocols such as RIP are based on the Bellman-Ford idea, where each router repeatedly updates its distances using its neighbors' distances.
Currency arbitrage: convert exchange rates using
-log(rate)as edge weights. A negative cycle then means a sequence of trades that makes a profit. Bellman-Ford can find it.Distance tables: Floyd-Warshall can precompute the travel distance between every pair of cities, stations, or rooms in a building.
Transitive closure: a version of Floyd-Warshall (Warshall's algorithm) answers "can i reach j at all?" for every pair.
Common Mistakes
1. Forgetting the INF Check
In Bellman-Ford, relaxing from a vertex with dist = Integer.MAX_VALUE overflows. Always check dist[u] != INF first.
2. Running Only V - 2 Passes (Off by One)
Make sure the main loop runs exactly V - 1 times, then do a separate check pass for negative cycles.
3. Wrong Loop Order in Floyd-Warshall
The intermediate vertex k must be the outer loop.
4. Forgetting dist[i][i] = 0
If the diagonal is left as INF, then dist[i][i] will not be 0 at the end. It either stays INF or becomes the length of the shortest cycle through i, which is not the distance from a vertex to itself.
5. Using Negative Edges in an Undirected Graph
Any negative undirected edge is already a negative cycle.
6. Using Floyd-Warshall for Large Graphs
O(V³) grows very fast. Check the constraints first.
Interview Tips and Practice Problems
Interviewers often ask:
"Why does Dijkstra fail with negative weights, and what would you use instead?"
"Why does Bellman-Ford run V - 1 passes?"
"How do you detect a negative cycle?"
"Why must
kbe the outermost loop in Floyd-Warshall?"
Good problems to practice:
Cheapest Flights Within K Stops (LeetCode 787) – a Bellman-Ford variant limited to K + 1 passes
Network Delay Time (LeetCode 743) – try solving it with both Dijkstra and Bellman-Ford
Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334) – Floyd-Warshall
Evaluate Division (LeetCode 399) – can be solved with a Floyd-Warshall style update
Negative Weight Cycle (GeeksforGeeks)
The Main Idea
Bellman-Ford solves single-source shortest paths even with negative edges:
dist[source] = 0, others = ∞
↓
Relax ALL edges, V - 1 times
↓
One more pass: if anything improves → negative cycleFloyd-Warshall solves all-pairs shortest paths:
for k: (intermediate vertex)
for i:
for j:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])Their complexities are:
Bellman-Ford → O(V · E) time, O(V) space
Floyd-Warshall → O(V³) time, O(V²) spaceRemember these four things:
1. Negative edges are fine; negative cycles make shortest paths undefined.
2. Bellman-Ford needs V - 1 passes because a shortest path has at most V - 1 edges.
3. Floyd-Warshall: k must be the outermost loop.
4. Negative cycle check: extra Bellman-Ford pass, or dist[i][i] < 0 in Floyd-Warshall.Use Dijkstra when weights are non-negative, Bellman-Ford when they can be negative, and Floyd-Warshall when you need every pair and the graph is small.