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
itojfor every pairi, j. - Distance matrix: an
n × ntable 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 tryi → k → j(Robert Floyd and Stephen Warshall, 1962). - Dynamic programming: building big answers from smaller answers we already stored. Here: the best
i → jthrough cities0..kis built from the besti → kandk → jthrough cities0..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 than2^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
- Start with direct roads only:
dist[i][j]= the road length, ∞ where there is no road, 0 on the diagonal. - Now allow city
kas a place to pass through. For every pair, the one new option isi → k → j, which costsdist[i][k] + dist[k][j]. Both halves don't needkin their middle, so they are already right in the table. Keep the smaller. - Do that for
k = 0, 1, …, n - 1. After the lastk, 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
- What does
dist[i][j]mean after stepk? The shortesti → jdistance using only cities0..kas via-cities. - Why must
kbe the outer loop? Stepkneedsdist[i][k]anddist[k][j]to be final for via-cities0..k-1; withkinside, pairs are finished too early. - Complexity? O(n³) time, O(n²) space.
- 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).
- How do you detect a negative cycle? After the loops, any
dist[i][i] < 0. - How do you rebuild a path? Keep
next[i][j]; follow it fromiuntilj. - Why can't you use
Integer.MAX_VALUEas 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 × ndistance 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
koutside,INF = 10^9(soINF + INFfits), 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.