Implement Floyd Warshall Algorithm

The problem, simply

You get V towns and one-way roads with prices. Some prices may be negative, but there is no loop whose prices add up to less than zero.

Fill a table where cell [i][j] is the cheapest price to get from town i to town j, for every pair of towns at once. If there is no way, the cell says infinity.

A story to remember it

Picture it

Examples

Way 1: the simple way

Run a single-start shortest path method from every town. Because roads can be negative, use Bellman Ford: from each start, relax every road V - 1 times.

1. For each start s, set dist[s][s] = 0 and the rest to infinity.
2. Repeat V - 1 times: for every road u > v with price w, try dist[s][u] + w for dist[s][v].

import java.util.*;

class Solution {
    static final int INF = 1_000_000_000;

    public int[][] allPairs(int V, int[][] edges) {
        int[][] dist = new int[V][V];
        for (int s = 0; s < V; s++) {
            Arrays.fill(dist[s], INF);
            dist[s][s] = 0;
            for (int round = 1; round < V; round++) {      // Bellman Ford from s
                for (int[] e : edges) {
                    int u = e[0], v = e[1], w = e[2];
                    if (dist[s][u] != INF && dist[s][u] + w < dist[s][v]) {
                        dist[s][v] = dist[s][u] + w;
                    }
                }
            }
        }
        return dist;
    }
}

How long it takes: V starts, each doing V - 1 rounds over E roads, O(V^2 * E). In a busy map E is close to V^2, so that is O(V^4). Extra room: the table, O(V^2). If no road is negative, running Dijkstra from every town is faster, O(V * E log V).

Way 2: the clever way

Let the towns take turns being the changing town. When town k gets its turn, every cell asks one question:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

The left half of the trip, i to k, sits in column k of row i. The right half, k to j, sits in row k. Both halves already use only the changing towns before k, so after town k's turn, every cell knows the cheapest trip that changes only at towns 0 to k.

1. Copy the direct prices into the table. Put 0 on the diagonal and infinity where there is no road.
2. For k from 0 to V - 1, for every i, for every j: try going through k.
3. Afterwards, any negative number on the diagonal means a negative loop.

import java.util.*;

class Solution {
    static final int INF = 1_000_000_000;

    // returns null when there is a negative loop
    public int[][] floydWarshall(int V, int[][] edges) {
        int[][] dist = new int[V][V];
        for (int i = 0; i < V; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }
        for (int[] e : edges) dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);

        for (int k = 0; k < V; k++) {               // k must be the outer loop
            for (int i = 0; i < V; i++) {
                if (dist[i][k] == INF) continue;    // no way to reach k from i
                for (int j = 0; j < V; j++) {
                    if (dist[k][j] == INF) continue;
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        for (int i = 0; i < V; i++) if (dist[i][i] < 0) return null;   // negative loop
        return dist;
    }
}

How long it takes: three loops of V each, O(V^3). Extra room: the table, O(V^2). It updates the table in place; row k and column k do not change during turn k, so reading and writing the same table is safe.

Watch out for

• Using Integer.MAX_VALUE for infinity. Adding two of them overflows. Use a big number like 1_000_000_000 and skip cells that are infinity.
• Two roads between the same towns. Keep the cheaper one when you fill the table.
• Forgetting the 0 on the diagonal. Without it, the trip from a town to itself looks impossible.
• GeeksforGeeks gives a matrix with -1 for no road. Turn -1 into infinity first, then back into -1 at the end.

What interviewers ask next

• How do you print the actual route? Keep next[i][j], the first town after i. When going through k wins, set next[i][j] = next[i][k], then follow next from i to j.
• Which pairs can reach each other at all? Use the same three loops with true and false: reach[i][j] |= reach[i][k] && reach[k][j]. That is the transitive closure.
• Floyd Warshall or Dijkstra from every town? With few roads and no negative prices, Dijkstra from every town, O(V * E log V), wins. With many roads or negative prices, the simple O(V^3) loops are hard to beat.
• Find the city with the fewest neighbours within a distance limit (LeetCode 1334)? Fill the table with Floyd Warshall, then count each row.
• Why is it dynamic programming? Each turn reuses the answers of the previous turn: the best trip using middle towns up to k is built from best trips using towns up to k - 1.

Remember this

Grown-up words: towns are vertices, roads are directed weighted edges, the price table is the distance matrix, the changing town is the intermediate vertex, and filling the table this way is the Floyd Warshall algorithm, an all pairs shortest path method built on dynamic programming.