WikiGalaxy
Graph Floyd-Warshall Algorithm
Introduction
The Floyd-Warshall algorithm is a dynamic programming technique used to find the shortest paths between all pairs of vertices in a weighted graph. It is particularly useful for dense graphs and can handle negative weights, provided there are no negative cycles.
Algorithm Steps
The algorithm works by iteratively improving the path estimates. Initially, the shortest path between any two vertices is the direct edge between them. The algorithm then considers each vertex as an intermediate point and updates the path lengths accordingly.
public class FloydWarshall {
final static int INF = 99999;
void floydWarshall(int graph[][], int V) {
int dist[][] = new int[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist, V);
}
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();
}
}
}
Example 1: Basic Graph
Consider a graph with 4 vertices and the following adjacency matrix:
Graph:
0 5 INF 10
INF 0 3 INF
INF INF 0 1
INF INF INF 0
After applying the Floyd-Warshall algorithm, the shortest paths between all pairs of vertices are computed.
Console Output:
0 5 8 9 INF 0 3 4 INF INF 0 1 INF INF INF 0
Example 2: Graph with Negative Weights
Graph Description
This example demonstrates a graph with negative weights but no negative cycles. The adjacency matrix is:
Graph:
0 3 INF INF
2 0 INF INF
INF 7 0 1
6 INF -2 0
The algorithm will correctly compute the shortest paths despite the negative weights.
public class FloydWarshallNegative {
final static int INF = 99999;
void floydWarshall(int graph[][], int V) {
int dist[][] = new int[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist, V);
}
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();
}
}
}
Console Output:
0 3 INF INF 2 0 INF INF 8 7 0 1 6 9 -2 0
Example 3: Graph with Multiple Paths
Graph Description
In this example, the graph contains multiple paths between some pairs of nodes. The adjacency matrix is:
Graph:
0 1 4 INF
INF 0 2 6
INF INF 0 3
INF INF INF 0
The Floyd-Warshall algorithm will find the shortest paths by considering all possible intermediate vertices.
public class FloydWarshallMultiplePaths {
final static int INF = 99999;
void floydWarshall(int graph[][], int V) {
int dist[][] = new int[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist, V);
}
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();
}
}
}
Console Output:
0 1 3 6 INF 0 2 5 INF INF 0 3 INF INF INF 0
Example 4: Dense Graph
Graph Description
A dense graph is characterized by having many edges. This example shows how the Floyd-Warshall algorithm efficiently computes shortest paths in such graphs. The adjacency matrix is:
Graph:
0 2 9 10
1 0 6 4
INF INF 0 7
INF INF 3 0
The algorithm's complexity is O(V^3), making it suitable for dense graphs.
public class FloydWarshallDenseGraph {
final static int INF = 99999;
void floydWarshall(int graph[][], int V) {
int dist[][] = new int[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist, V);
}
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();
}
}
}
Console Output:
0 2 8 6 1 0 6 4 INF INF 0 7 INF INF 3 0
Example 5: Sparse Graph
Graph Description
Sparse graphs have fewer edges relative to the number of vertices. The Floyd-Warshall algorithm still performs well, though it may not be as efficient as other algorithms for sparse graphs. The adjacency matrix is:
Graph:
0 INF INF 1
INF 0 INF INF
INF INF 0 5
INF 2 INF 0
This example highlights the algorithm's ability to find paths even when direct connections are limited.
public class FloydWarshallSparseGraph {
final static int INF = 99999;
void floydWarshall(int graph[][], int V) {
int dist[][] = new int[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
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] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist, V);
}
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();
}
}
}
Console Output:
0 3 INF 1 INF 0 INF INF INF 7 0 5 INF 2 INF 0
