SyntaxPilot
Courses/DSA and Coding Problems/Lesson 54
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 54 of 90

Floyd-Warshall: all-pairs shortest paths

queued

These are the notes for DSA episode 54. Dijkstra (episode 52) and Bellman-Ford (episode 53) start from one city. Today we want the shortest distance from every city to every other city: the distance chart at the back of a road atlas. We start from a real-life problem (Ravi's trial launch), define every word, try the obvious idea (every path from every city: correct, but Time Limit Exceeded on only 15 cities), find the key insight (allow one more "via" city at a time; dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])), and finish with Floyd-Warshall: three loops, O(n³). Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

Old road atlases have a chart at the back: the shortest road distance from every city to every other city. Find the row for Jaipur and the column for Pune, and there it is. Ravi runs a food delivery startup and wants a small trial launch. His delivery range is a fixed distance, so he wants the city with the fewest other cities within range, so the trial stays small. To answer that, he needs the whole chart.

With the atlas In code
A city a vertex 0..n-1
A two-way road of length w an undirected weighted edge {a, b, w}
The distance chart the distance matrix dist[i][j]
A city to itself dist[i][i] = 0
Delivery range distanceThreshold
No road at all dist[i][j] = ∞

Every word, from zero

  • All-pairs shortest paths: the shortest distance from i to j for every pair i, j.
  • Distance matrix: an n × n table holding those distances, like the atlas chart.
  • Via-city (intermediate vertex): a city a route passes through on its way.
  • Floyd-Warshall: allow the cities as via-cities one at a time (k = 0, 1, …, n - 1), and for every pair try i → k → j (Robert Floyd and Stephen Warshall, 1962).
  • Dynamic programming: building big answers from smaller answers we already stored. Here: the best i → j through cities 0..k is built from the best i → k and k → j through cities 0..k-1.
  • Backtracking: in a DFS, taking a city off the current path when we return, so other paths may use it.
  • Factorial (n!): n × (n - 1) × … × 1; it grows even faster than 2^n.
  • Negative cycle: a loop whose weights add up below 0; it shows up as dist[i][i] < 0.

Problem statement

LeetCode 1334, Find the City With the Smallest Number of Neighbors at a Threshold Distance. There are n cities 0..n-1 and edges[i] = [from, to, weight], a two-way road. Return the city with the smallest number of cities reachable with a shortest distance ≤ distanceThreshold. If there is a tie, return the city with the greatest number.

n edges threshold Answer
4 [[0,1,3],[1,2,1],[1,3,4],[2,3,1]] 4 3
5 [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]] 2 0

Constraints: 2 ≤ n ≤ 100, 1 ≤ weight, distanceThreshold ≤ 10^4, all pairs distinct.

Example 1 by hand: from city 0, city 1 is 3 away and city 2 is 4 (through 1); city 3 is 5 (out of range): 2 cities. City 1 reaches 0, 2, 3: 3. City 2 reaches 0, 1, 3: 3. City 3 reaches 1 and 2: 2. Cities 0 and 3 tie with 2, so the answer is the bigger number, 3.

Every version below uses the same pick step: count the cities in range for each city, keep the fewest, and use <= so a tie goes to the bigger number.

    static int pick(int[][] dist, int n, int threshold) {
        int best = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && dist[i][j] <= threshold) count++;
            if (count <= fewest) { fewest = count; best = i; }
        }
        return best;
    }

Obvious idea: from every city, try every path

For every start s, a DFS walks every simple path (no city twice), keeps the smallest distance seen for each city, and backtracks.

import java.util.*;

public class Main {
    static int pick(int[][] dist, int n, int threshold) {
        int best = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && dist[i][j] <= threshold) count++;
            if (count <= fewest) { fewest = count; best = i; }
        }
        return best;
    }
    static int findTheCity(int n, int[][] edges, int threshold) {
        int[][] w = new int[n][n];
        for (int[] row : w) Arrays.fill(row, -1);
        for (int[] e : edges) { w[e[0]][e[1]] = e[2]; w[e[1]][e[0]] = e[2]; }
        int[][] dist = new int[n][n];
        for (int s = 0; s < n; s++) {
            Arrays.fill(dist[s], Integer.MAX_VALUE);
            dfs(w, n, s, 0, new boolean[n], dist[s]);
        }
        return pick(dist, n, threshold);
    }
    static void dfs(int[][] w, int n, int u, int d, boolean[] seen, int[] best) {
        best[u] = Math.min(best[u], d);
        seen[u] = true;
        for (int v = 0; v < n; v++)
            if (w[u][v] >= 0 && !seen[v]) dfs(w, n, v, d + w[u][v], seen, best);
        seen[u] = false;
    }
    public static void main(String[] args) {
        int[][] ex1 = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
        int[][] ex2 = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3},
                       {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
        System.out.println(findTheCity(4, ex1, 4));
        System.out.println(findTheCity(5, ex2, 2));
    }
}
3
0

Correct. Now 15 cities with a road between every pair:

import java.util.*;

public class Main {
    static int pick(int[][] dist, int n, int threshold) {
        int best = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && dist[i][j] <= threshold) count++;
            if (count <= fewest) { fewest = count; best = i; }
        }
        return best;
    }
    static int findTheCity(int n, int[][] edges, int threshold) {
        int[][] w = new int[n][n];
        for (int[] row : w) Arrays.fill(row, -1);
        for (int[] e : edges) { w[e[0]][e[1]] = e[2]; w[e[1]][e[0]] = e[2]; }
        int[][] dist = new int[n][n];
        for (int s = 0; s < n; s++) {
            Arrays.fill(dist[s], Integer.MAX_VALUE);
            dfs(w, n, s, 0, new boolean[n], dist[s]);
        }
        return pick(dist, n, threshold);
    }
    static void dfs(int[][] w, int n, int u, int d, boolean[] seen, int[] best) {
        best[u] = Math.min(best[u], d);
        seen[u] = true;
        for (int v = 0; v < n; v++)
            if (w[u][v] >= 0 && !seen[v]) dfs(w, n, v, d + w[u][v], seen, best);
        seen[u] = false;
    }
    public static void main(String[] args) {
        int n = 15;
        List<int[]> roads = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) roads.add(new int[]{i, j, 1 + (i * 7 + j * 3) % 10});
        long t0 = System.nanoTime();
        int city = findTheCity(n, roads.toArray(new int[0][]), 4);
        System.out.println("city " + city + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}
Time Limit Exceeded (stopped after 8 seconds)

Why it explodes: from one city there are 14 roads, then 13, then 12…: about 14! ≈ 8,700 crore paths, from each city. And the waste: the same piece (say the best way from 3 to 7) is walked again inside millions of paths.

The key insight: one via-city at a time

  1. Start with direct roads only: dist[i][j] = the road length, ∞ where there is no road, 0 on the diagonal.
  2. Now allow city k as a place to pass through. For every pair, the one new option is i → k → j, which costs dist[i][k] + dist[k][j]. Both halves don't need k in their middle, so they are already right in the table. Keep the smaller.
  3. Do that for k = 0, 1, …, n - 1. After the last k, any route is allowed: the table is complete.

Loop order matters: k must be the outer loop. It is the step number ("cities 0..k are allowed"). With k inside, a pair is finished before the pieces it needs exist (bug 1).

The optimal solution in Java: Floyd-Warshall

    static int findTheCity(int n, int[][] edges, int threshold) {
        int INF = 1_000_000_000;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; 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]);
            dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        return pick(dist, n, threshold);
    }

INF = 1_000_000_000, not Integer.MAX_VALUE, so that INF + INF (two billion) still fits in an int. Tests: the two examples, a town with no roads at all, and threshold 0:

import java.util.*;

public class Main {
    static int pick(int[][] dist, int n, int threshold) {
        int best = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && dist[i][j] <= threshold) count++;
            if (count <= fewest) { fewest = count; best = i; }
        }
        return best;
    }
    static int findTheCity(int n, int[][] edges, int threshold) {
        int INF = 1_000_000_000;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; 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]);
            dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        return pick(dist, n, threshold);
    }
    public static void main(String[] args) {
        int[][] ex1 = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
        int[][] ex2 = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3},
                       {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
        System.out.println(findTheCity(4, ex1, 4));
        System.out.println(findTheCity(5, ex2, 2));
        System.out.println(findTheCity(3, new int[][]{{0, 1, 5}}, 10));
        System.out.println(findTheCity(3, new int[][]{{0, 1, 1}, {1, 2, 1}}, 0));
    }
}
3
0
2
2

With no roads (or threshold 0), every city reaches 0 others; on a tie we take the biggest number, 2. The 15 cities that timed out:

city 9, 0 ms

LeetCode's biggest: 100 cities and a road between every pair (4,950 roads), a million steps:

import java.util.*;

public class Main {
    static int pick(int[][] dist, int n, int threshold) {
        int best = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && dist[i][j] <= threshold) count++;
            if (count <= fewest) { fewest = count; best = i; }
        }
        return best;
    }
    static int findTheCity(int n, int[][] edges, int threshold) {
        int INF = 1_000_000_000;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; 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]);
            dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        return pick(dist, n, threshold);
    }
    public static void main(String[] args) {
        int n = 100;
        List<int[]> roads = new ArrayList<>();
        Random rnd = new Random(7);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) roads.add(new int[]{i, j, 1 + rnd.nextInt(10000)});
        long t0 = System.nanoTime();
        int city = findTheCity(n, roads.toArray(new int[0][]), 2000);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(roads.size() + " roads: city " + city + ", " + ms + " ms");
    }
}
4950 roads: city 99, 6 ms

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

// Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334): Floyd-Warshall.
int findTheCity(int n, vector<vector<int>>& edges, int threshold) {
    const int INF = 1000000000;                       // INF + INF still fits in an int
    vector<vector<int>> dist(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (auto& e : edges) {                           // two-way roads
        dist[e[0]][e[1]] = min(dist[e[0]][e[1]], e[2]);
        dist[e[1]][e[0]] = min(dist[e[1]][e[0]], e[2]);
    }
    for (int k = 0; k < n; k++)                       // k (the via-city) is the OUTER loop
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    int best = -1, fewest = INT_MAX;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++)
            if (j != i && dist[i][j] <= threshold) count++;
        if (count <= fewest) { fewest = count; best = i; }   // <= : a tie goes to the bigger number
    }
    return best;
}

int main() {
    vector<vector<int>> ex1 = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
    vector<vector<int>> ex2 = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
    cout << findTheCity(4, ex1, 4) << "\n";
    cout << findTheCity(5, ex2, 2) << "\n";
}
3
0

The same solution in Python

# Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334): Floyd-Warshall.
def find_the_city(n, edges, threshold):
    INF = float("inf")
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for a, b, w in edges:                      # two-way roads
        dist[a][b] = min(dist[a][b], w)
        dist[b][a] = min(dist[b][a], w)
    for k in range(n):                         # k (the via-city) is the OUTER loop
        for i in range(n):
            dik = dist[i][k]
            for j in range(n):
                if dik + dist[k][j] < dist[i][j]:
                    dist[i][j] = dik + dist[k][j]
    best, fewest = -1, n + 1
    for i in range(n):
        count = sum(1 for j in range(n) if j != i and dist[i][j] <= threshold)
        if count <= fewest:                    # <= : a tie goes to the bigger number
            best, fewest = i, count
    return best

print(find_the_city(4, [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]], 4))
print(find_the_city(5, [[0, 1, 2], [0, 4, 8], [1, 2, 3], [1, 4, 2], [2, 3, 1], [3, 4, 1]], 2))
3
0

Three real bugs

The first bug uses a floyd function that returns the whole matrix, on a chain of roads 0 - 2, 2 - 3, 3 - 1 (length 1 each), and prints dist[0][1] (should be 3).

Bug 1: k as the inner loop

import java.util.*;

public class Main {
    static int[][] floyd(int n, int[][] edges) {
        int INF = 1_000_000_000;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; 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]);
            dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        return dist;
    }
    public static void main(String[] args) {
        System.out.println("0 to 1: " + floyd(4, new int[][]{{0, 2, 1}, {2, 3, 1}, {3, 1, 1}})[0][1]);
    }
}
0 to 1: 1000000000

One billion: "unreachable". When pair (0, 1) is processed, it needs dist[2][1] or dist[0][3], which are not computed yet, and (0, 1) is never looked at again. With k outside:

0 to 1: 3

Bug 2: roads stored in one direction only

import java.util.*;

public class Main {
    static int pick(int[][] dist, int n, int threshold) {
        int best = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && dist[i][j] <= threshold) count++;
            if (count <= fewest) { fewest = count; best = i; }
        }
        return best;
    }
    static int findTheCity(int n, int[][] edges, int threshold) {
        int INF = 1_000_000_000;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; 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 < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        return pick(dist, n, threshold);
    }
    public static void main(String[] args) {
        int[][] ex1 = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
        int[][] ex2 = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3},
                       {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
        System.out.println(findTheCity(4, ex1, 4));
        System.out.println(findTheCity(5, ex2, 2));
    }
}
3
4

4 instead of 0 for example 2: the roads are two-way, but the matrix only has one direction. Fix: set both dist[a][b] and dist[b][a].

Bug 3: Integer.MAX_VALUE as infinity

import java.util.*;

public class Main {
    static int pick(int[][] dist, int n, int threshold) {
        int best = -1, fewest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (j != i && dist[i][j] <= threshold) count++;
            if (count <= fewest) { fewest = count; best = i; }
        }
        return best;
    }
    static int findTheCity(int n, int[][] edges, int threshold) {
        int INF = Integer.MAX_VALUE;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; 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]);
            dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        return pick(dist, n, threshold);
    }
    public static void main(String[] args) {
        int[][] ex1 = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
        int[][] ex2 = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3},
                       {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
        System.out.println(findTheCity(4, ex1, 4));
        System.out.println(findTheCity(5, ex2, 2));
    }
}
3
4

∞ + ∞ overflows to a negative number, which looks like a very short path, and the matrix fills with nonsense. Fix: INF = 1_000_000_000, or check dist[i][k] < INF && dist[k][j] < INF first.

Negative weights and negative cycles

On one-way edges, Floyd-Warshall is fine with negative weights as long as there is no negative cycle. If city i is on a negative cycle, going round it gives a path from i back to i shorter than zero, so dist[i][i] < 0 after the loops. A one-way graph 0 → 1 (4), 1 → 2 (-3), 2 → 1 (1): the loop 1 → 2 → 1 totals -2.

import java.util.*;

public class Main {
    static int[][] floydDirected(int n, int[][] edges) {
        int INF = 1_000_000_000;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; 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 < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        return dist;
    }
    public static void main(String[] args) {
        int[][] d = floydDirected(3, new int[][]{{0, 1, 4}, {1, 2, -3}, {2, 1, 1}});
        for (int i = 0; i < 3; i++)
            System.out.println("dist[" + i + "][" + i + "] = " + d[i][i]);
    }
}
dist[0][0] = 0
dist[1][1] = -2
dist[2][2] = -4

Cities 1 and 2 are on the negative cycle. (With two-way roads, any negative road is itself a negative cycle: go there and back.)

Complexity

Approach Time Space Test
Every path from every city O(n × n!) O(n²) 15 cities: Time Limit Exceeded
Floyd-Warshall O(n³) O(n²) 100 cities: a few ms
Dijkstra from every city O(n × (V + E) log V) O(V + E) faster on big sparse graphs; no negative weights
Bellman-Ford from every city O(n × V × E) O(V) slow; only for negative weights without FW

Three nested loops of n: n³ steps; the matrix is n² numbers. For n = 100, a million steps.

Common mistakes

Mistake What you see (real) Why Fix
k as the inner loop 1000000000 instead of 3 uses pieces not computed yet k outermost
Road stored one way 4 instead of 0 roads are two-way set [a][b] and [b][a]
INF = Integer.MAX_VALUE 4 instead of 0 ∞ + ∞ overflows INF = 10^9, or a check
dist[i][i] not set to 0 wrong counts a city to itself is 0 zero the diagonal
< instead of <= in pick the smaller city on a tie LeetCode wants the bigger count <= fewest
Two roads for one pair the longer one kept later input overwrote Math.min

Mini project: the atlas distance chart

Shortest road distance (km) between every pair of five North Indian cities, printed as the chart at the back of an atlas. (Distances are rounded, for practice.)

import java.util.*;

public class Main {
    // Mini project: the atlas distance chart. Shortest road distance (km) between every pair of cities.
    public static void main(String[] args) {
        String[] city = {"Delhi", "Agra", "Jaipur", "Lucknow", "Chandigarh"};
        int[][] roads = {{0, 1, 230}, {0, 2, 280}, {1, 2, 240}, {1, 3, 335}, {0, 4, 245}, {0, 3, 555}};
        int n = city.length, INF = 1_000_000_000;
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) { Arrays.fill(d[i], INF); d[i][i] = 0; }
        for (int[] r : roads) { d[r[0]][r[1]] = Math.min(d[r[0]][r[1]], r[2]); d[r[1]][r[0]] = Math.min(d[r[1]][r[0]], r[2]); }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        System.out.printf("%-11s", "");
        for (String c : city) System.out.printf("%11s", c);
        System.out.println();
        for (int i = 0; i < n; i++) {
            System.out.printf("%-11s", city[i]);
            for (int j = 0; j < n; j++) System.out.printf("%11d", d[i][j]);
            System.out.println();
        }
    }
}
                 Delhi       Agra     Jaipur    Lucknow Chandigarh
Delhi                0        230        280        555        245
Agra               230          0        240        335        475
Jaipur             280        240          0        575        525
Lucknow            555        335        575          0        800
Chandigarh         245        475        525        800          0

Agra to Chandigarh has no direct road here, so the chart goes through Delhi: 230 + 245 = 475.

Practice

1. Network Delay Time (LeetCode 743) with Floyd-Warshall.

Solution

One-way links, 1-based towers; the answer is the biggest value in row k.

import java.util.*;

public class Main {
    // Network Delay Time (LeetCode 743) with Floyd-Warshall: one-way links, then the max over row k.
    static int networkDelayTime(int[][] times, int n, int k) {
        int INF = 1_000_000_000;
        int[][] d = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) { Arrays.fill(d[i], INF); d[i][i] = 0; }
        for (int[] t : times) d[t[0]][t[1]] = Math.min(d[t[0]][t[1]], t[2]);
        for (int via = 1; via <= n; via++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (d[i][via] + d[via][j] < d[i][j]) d[i][j] = d[i][via] + d[via][j];
        int ans = 0;
        for (int v = 1; v <= n; v++) {
            if (d[k][v] >= INF) return -1;
            ans = Math.max(ans, d[k][v]);
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 1));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 2));
    }
}
2
1
-1

2. Evaluate Division (LeetCode 399).

Solution

a / b = 2 is an edge a → b of weight 2 and b → a of weight 1/2. Floyd-Warshall with multiply instead of add fills every ratio.

import java.util.*;

public class Main {
    // Evaluate Division (LeetCode 399): a / b = 2 means an edge a → b with weight 2 and b → a with 1/2.
    // Floyd-Warshall with "multiply" instead of "add": r[i][j] = r[i][k] * r[k][j].
    public static void main(String[] args) {
        String[][] eq = {{"a", "b"}, {"b", "c"}};
        double[] val = {2.0, 3.0};
        String[][] queries = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
        Map<String, Integer> id = new HashMap<>();
        for (String[] e : eq) for (String s : e) id.putIfAbsent(s, id.size());
        int n = id.size();
        double[][] r = new double[n][n];
        for (double[] row : r) Arrays.fill(row, -1.0);
        for (int i = 0; i < n; i++) r[i][i] = 1.0;
        for (int i = 0; i < eq.length; i++) {
            int a = id.get(eq[i][0]), b = id.get(eq[i][1]);
            r[a][b] = val[i]; r[b][a] = 1.0 / val[i];
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (r[i][j] < 0 && r[i][k] > 0 && r[k][j] > 0) r[i][j] = r[i][k] * r[k][j];
        for (String[] q : queries) {
            Integer a = id.get(q[0]), b = id.get(q[1]);
            System.out.println(q[0] + " / " + q[1] + " = " + (a == null || b == null ? -1.0 : r[a][b]));
        }
    }
}
a / c = 6.0
b / a = 0.5
a / e = -1.0
a / a = 1.0
x / x = -1.0

3. Print the shortest path itself, not just its length.

Solution

Keep next[i][j] = the first city after i on the way to j. When i → k → j is better, next[i][j] = next[i][k].

import java.util.*;

public class Main {
    // Print the path itself: next[i][j] = the first city after i on the shortest way to j.
    public static void main(String[] args) {
        int n = 4, INF = 1_000_000_000;
        int[][] roads = {{0, 2, 1}, {2, 3, 1}, {3, 1, 1}, {0, 1, 5}};
        int[][] d = new int[n][n], next = new int[n][n];
        for (int i = 0; i < n; i++) { Arrays.fill(d[i], INF); Arrays.fill(next[i], -1); d[i][i] = 0; next[i][i] = i; }
        for (int[] r : roads) {
            d[r[0]][r[1]] = r[2]; next[r[0]][r[1]] = r[1];
            d[r[1]][r[0]] = r[2]; next[r[1]][r[0]] = r[0];
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; next[i][j] = next[i][k]; }
        List<Integer> path = new ArrayList<>();
        for (int x = 0; x != 1; x = next[x][1]) path.add(x);
        path.add(1);
        System.out.println("0 to 1: " + d[0][1] + " via " + path);
    }
}
0 to 1: 3 via [0, 2, 3, 1]

4. Detect a negative cycle on your own graph.

Solution

Use long and an infinity check (negative weights make the "INF + something" trick unsafe), then look at the diagonal.

import java.util.*;

public class Main {
    // Detect a negative cycle: after Floyd-Warshall, dist[i][i] < 0 for every city on (or reaching) one.
    static boolean hasNegativeCycle(int n, int[][] edges) {
        long INF = Long.MAX_VALUE / 4;
        long[][] d = new long[n][n];
        for (int i = 0; i < n; i++) { Arrays.fill(d[i], INF); d[i][i] = 0; }
        for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    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];
        for (int i = 0; i < n; i++) if (d[i][i] < 0) return true;
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasNegativeCycle(3, new int[][]{{0, 1, 4}, {1, 2, -3}, {2, 0, 1}}));
        System.out.println(hasNegativeCycle(3, new int[][]{{0, 1, 4}, {1, 2, -3}, {2, 1, 1}}));
    }
}
false
true

Quick quiz

Two-way roads: 0 - 1 (2), 1 - 2 (2), 2 - 3 (2), 0 - 3 (9), 1 - 3 (5). After Floyd-Warshall, dist[0][3]? A) 6 B) 7 C) 9 D) 5

Answer

A) 6. 0 → 1 → 2 → 3 = 2 + 2 + 2 = 6, shorter than 0 → 1 → 3 = 7 and the direct 9.

Interview questions

  1. What does dist[i][j] mean after step k? The shortest i → j distance using only cities 0..k as via-cities.
  2. Why must k be the outer loop? Step k needs dist[i][k] and dist[k][j] to be final for via-cities 0..k-1; with k inside, pairs are finished too early.
  3. Complexity? O(n³) time, O(n²) space.
  4. Floyd-Warshall or Dijkstra from every vertex? Dijkstra × n is O(n (V + E) log V): better on big sparse graphs with non-negative weights. Floyd-Warshall is simpler, handles negative weights, and is great for small dense graphs (n ≤ a few hundred).
  5. How do you detect a negative cycle? After the loops, any dist[i][i] < 0.
  6. How do you rebuild a path? Keep next[i][j]; follow it from i until j.
  7. Why can't you use Integer.MAX_VALUE as infinity? ∞ + ∞ overflows to a negative number.

Glossary

Term Meaning
All-pairs shortest paths Shortest distance for every pair of vertices
Distance matrix The n × n table dist[i][j]
Via-city A city a route passes through
Floyd-Warshall Allow via-cities one at a time; try i → k → j for every pair
Dynamic programming Big answers from stored smaller answers
Threshold The maximum distance that counts as "in range"
Backtracking Undo a choice (un-visit a city) when returning in a DFS
Factorial n × (n - 1) × … × 1
Negative cycle A loop with total weight below 0; dist[i][i] < 0
O(n³) Three nested loops over n

Summary

  • All-pairs shortest paths fill an n × n distance matrix. Trying every path from every city is factorial.
  • Floyd-Warshall: for k (outer), i, j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). O(n³) time, O(n²) space.
  • Keep k outside, INF = 10^9 (so INF + INF fits), roads in both directions, and 0 on the diagonal.
  • Negative weights are fine; a negative cycle shows up as dist[i][i] < 0.
  • Next episode: Union-Find, which cities are connected at all, almost instantly.