Introduction

The Floyd-Warshall algorithm is a classic algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It’s especially useful for dense graphs and can handle both positive and negative edge weights (though not negative cycles).

Algorithm

  1. Initialization:
    • Create a distance matrix dist where dist[i][j] is the initial weight of the edge from vertex i to vertex j, or infinity if no edge exists. Set dist[i][i] = 0 for all vertices i.
  2. Dynamic Programming Update:
    • For each intermediate vertex k, update the distance matrix to consider paths that pass through vertex k.
    • For each pair of vertices (i, j), compute if a shorter path exists by going through k: if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; }
  3. Result:
    • After processing all vertices, dist[i][j] will contain the shortest path distance from vertex i to vertex j.

Pseudocode

 function floydWarshall(graph):
     dist = matrix of size VxV, initially filled with graph weights (or infinity if no edge exists)
     for each vertex v:
         dist[v][v] = 0
 
     for each intermediate vertex k:
         for each source vertex i:
             for each destination vertex j:
                 if dist[i][k] + dist[k][j] < dist[i][j]:
                     dist[i][j] = dist[i][k] + dist[k][j]
 
     return dist

Code

Java

public class FloydWarshall {

	private static final int INF = Integer.MAX_VALUE; // A large value representing infinity
	public static void floydWarshall(int[][] graph) {
		int V = graph.length;
		int[][] dist = new int[V][V];

		// Initialize the distance matrix
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
				dist[i][j] = graph[i][j];
			}
		}

		// Update the distance matrix considering each vertex as an intermediate vertex
		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];
					}
				}
			}
		}

		// Print the final distance matrix
		printSolution(dist);
	}

	private static void printSolution(int[][] dist) {
		int V = dist.length;
		System.out.println("Shortest distances matrix:");

		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();
		}
	}
}

Complexity

  • ⏰ Time complexity: O(V^3), where V is the number of vertices in the graph. This is due to the three nested loops each running V times.
  • 🧺 Space complexity: O(V^2) for storing the distance matrix.

Proof of Correctness

  • The algorithm starts by correctly initializing the distance matrix with direct edge weights and zero for self-loops.
  • It iteratively updates the shortest paths between all pairs of vertices by using each vertex as an intermediate point.
  • In each iteration, the algorithm ensures that any path from i to j through vertex k is considered and the minimum distance is updated with the rule:
    • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
  • By induction, after processing all vertices, dist[i][j] will correctly contain the shortest path distance between every pair of vertices i and j.
  • The Floyd-Warshall algorithm is thus guaranteed to provide the correct shortest paths for all pairs of vertices in the graph.

Transitive Closure

The transitive closure of a graph is a way to determine if there is a path between any two vertices. It indicates whether you can get from vertex i to vertex j through some sequence of edges.

Floyd-Warshall for Transitive Closure:

  • Use the Floyd-Warshall algorithm to compute the transitive closure by modifying the distance matrix to a reachability matrix.
  • Initialize the reachability matrix reach[i][j] to 1 if there is a direct edge between vertices i and j, otherwise 0. Set reach[i][i] to 1 by definition.

and the update rules are:

  • Use the standard Floyd-Warshall update rule to determine reachability:
    • reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])
  • For each pair of vertices (i, j), check if there is an indirect path through another vertex k.

Final Reachability:

  • After processing all vertices, reach[i][j] will be 1 if there is some path (direct or indirect) from i to j, otherwise 0.
for (int k = 0; k < V; k++) {
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
		}
	}
}

So, in conclusion, this modified Floyd-Warshall algorithm can effectively compute the transitive closure, indicating the reachability between all pairs of vertices in the graph.