Implement Floyd Warshall Algorithm
Problem Statement
Given a weighted directed graph with V vertices (edges can have negative weights but no negative cycles), find the shortest distances between every pair of vertices.
Example:
- Input:
V = 4 graph = [[0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1], [INF, INF, INF, 0]] - Output:
[[0, 5, 8, 9], [INF, 0, 3, 4], [INF, INF, 0, 1], [INF, INF, INF, 0]]
Noob-Friendly Explanation
Imagine you have a map of cities with one-way roads and distances. You want to know the shortest route between EVERY pair of cities — not just from one source, but from every city to every other city.
Floyd-Warshall asks a simple question for each pair (i, j): "Is it shorter to go directly from i to j, or to go from i to some middle city k and then from k to j?" It tries EVERY possible middle city.
Think of it like this: first try using city 0 as a layover. Then try using cities 0 and 1. Then 0, 1, and 2. Eventually, you've tried all possible layovers and found the shortest paths.
Approach 1: Brute Force (Run Dijkstra/Bellman-Ford from Each Vertex)
Intuition
Run Bellman-Ford from each vertex to find shortest paths from that vertex to all others. This gives all-pairs shortest paths but is less elegant.
Algorithm
- For each vertex v, run Bellman-Ford with v as source.
- Store all results in a V×V matrix.
import java.util.Arrays;
public class FloydWarshallBruteForce {
static final int INF = 99999;
public static int[][] allPairsShortestPath(int V, int[][] graph) {
int[][] dist = new int[V][V];
// Run Bellman-Ford from each vertex
for (int src = 0; src < V; src++) {
Arrays.fill(dist[src], INF);
dist[src][src] = 0;
// Collect edges from adjacency matrix
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (graph[i][j] != INF && i != j) {
// Edge from i to j with weight graph[i][j]
}
}
}
// Bellman-Ford V-1 relaxations
for (int iter = 0; iter < V - 1; iter++) {
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] != INF && dist[src][u] != INF
&& dist[src][u] + graph[u][v] < dist[src][v]) {
dist[src][v] = dist[src][u] + graph[u][v];
}
}
}
}
}
return dist;
}
public static void main(String[] args) {
int V = 4;
int[][] graph = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
int[][] result = allPairsShortestPath(V, graph);
for (int[] row : result) {
System.out.println(Arrays.toString(row));
}
}
}Complexity Analysis
- Time Complexity: O(V^3 × V) = O(V^4) — running Bellman-Ford (O(V^3) with adjacency matrix) from each of V vertices.
- Space Complexity: O(V^2) — for the distance matrix.
Approach 2: Optimal (Floyd-Warshall Algorithm)
Intuition
Use dynamic programming. For each intermediate vertex k, update all pairs (i, j): if going through k gives a shorter path, update it. After considering all intermediate vertices, we have all shortest paths.
The recurrence: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Algorithm
- Initialize
dist[][]as the input adjacency matrix. - For each intermediate vertex k (0 to V-1):
- For each pair (i, j):
- If
dist[i][k] + dist[k][j] < dist[i][j], updatedist[i][j].
- If
- For each pair (i, j):
- After all iterations,
dist[i][j]contains the shortest path from i to j.
import java.util.Arrays;
public class FloydWarshallOptimal {
static final int INF = 99999;
public static int[][] floydWarshall(int V, int[][] graph) {
int[][] dist = new int[V][V];
// Initialize distance matrix
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// Try every vertex as intermediate
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
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];
}
}
}
}
// Check for negative cycles (diagonal < 0)
for (int i = 0; i < V; i++) {
if (dist[i][i] < 0) {
System.out.println("Negative weight cycle detected!");
return new int[][]{};
}
}
return dist;
}
public static void printSolution(int[][] dist, int V) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF) {
System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
int V = 4;
int[][] graph = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
int[][] result = floydWarshall(V, graph);
printSolution(result, V);
// Output:
// 0 5 8 9
// INF 0 3 4
// INF INF 0 1
// INF INF INF 0
}
}Complexity Analysis
- Time Complexity: O(V^3) — three nested loops over V vertices.
- Space Complexity: O(V^2) — for the distance matrix.