Chapter 56 of 65

Bellman-Ford & Floyd-Warshall

On this page

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 cycles

Negative 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 -3

If 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] + w

The 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 times

Bellman-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 correct

So 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
   │                   ↑
   └───────────────────┘
             5

We 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 edges

Bellman-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 : -2

Together 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 j

It starts with only direct edges:

dist[i][i] = 0
dist[i][j] = weight of edge i → j, if it exists
dist[i][j] = ∞, otherwise

Then 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 : 2

Initial matrix:

      0    1    2    3
0     0    3    ∞    7
1     8    0    2    ∞
2     5    ∞    0    1
3     2    ∞    ∞    0

k = 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    ∞    0

k = 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    0

k = 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    0

k = 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    0

This 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: false

The 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 k

When 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 cycle

Reconstructing 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 vertex

Real-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 k be the outermost loop in Floyd-Warshall?"

Good problems to practice:

  1. Cheapest Flights Within K Stops (LeetCode 787) – a Bellman-Ford variant limited to K + 1 passes

  2. Network Delay Time (LeetCode 743) – try solving it with both Dijkstra and Bellman-Ford

  3. Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334) – Floyd-Warshall

  4. Evaluate Division (LeetCode 399) – can be solved with a Floyd-Warshall style update

  5. 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 cycle

Floyd-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²) space

Remember 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.