The Floyd-Warshall algorithm is a powerful technique for finding the shortest paths between all pairs of vertices in a weighted graph. Unlike Dijkstra's algorithm which finds shortest paths from a single source, Floyd-Warshall computes the shortest paths between every pair of vertices in just one execution. It can handle both positive and negative edge weights, though it requires that there are no negative cycles in the graph. The algorithm has a time complexity of O(V³), where V is the number of vertices, making it efficient for small to medium-sized graphs.
The first step of the Floyd-Warshall algorithm is to initialize the distance matrix. This matrix represents the shortest known distance between each pair of vertices. For initialization, we set the distance from each vertex to itself as zero, which forms the diagonal of our matrix. For vertices that have a direct edge between them, we set the distance to the weight of that edge. For vertices with no direct connection, we set the distance to infinity, indicating that we haven't found a path yet. This initialization creates our starting point, representing what we know about direct connections in the graph before considering any intermediate vertices.
The core of the Floyd-Warshall algorithm is a triple nested loop. The outermost loop iterates through each vertex k, considering it as a potential intermediate vertex in paths between all other pairs of vertices. For each intermediate vertex k, we check every possible pair of vertices i and j. The key insight is this: we compare the current known shortest path from i to j with a potential new path that goes from i to k and then from k to j. If this new path is shorter, we update our distance matrix. This simple comparison, dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), is the heart of the algorithm. By considering each vertex as an intermediate, we gradually build up the shortest paths between all pairs of vertices.
Let's trace through a specific example to see how the Floyd-Warshall algorithm works. Consider our graph with 5 vertices. Initially, we know the direct connections between vertices, but many paths are unknown and set to infinity. Now, let's consider vertex 1 as our intermediate vertex. For the path from vertex 0 to vertex 2, there's no direct connection, so dist[0][2] is infinity. But what if we go through vertex 1? The path from 0 to 1 has weight 3, and from 1 to 2 has weight 8, giving a total distance of 11. Since 11 is less than infinity, we update dist[0][2] to 11. This is how the algorithm discovers new paths - by considering each vertex as a potential stepping stone. After all iterations, our distance matrix will contain the shortest path between every pair of vertices.
The Floyd-Warshall algorithm has numerous practical applications. It's primarily used for finding the shortest paths between all pairs of vertices in a graph, but it can also detect negative cycles, compute transitive closure of graphs, and is used in network routing protocols and computer graphics. In terms of complexity, Floyd-Warshall runs in O(V³) time and requires O(V²) space, where V is the number of vertices. While this cubic time complexity might seem high, it's actually more efficient than running Dijkstra's algorithm V times for dense graphs. The algorithm's simplicity is one of its greatest strengths - with just a triple nested loop and a single comparison operation, it elegantly solves the all-pairs shortest paths problem. This makes Floyd-Warshall a fundamental algorithm in graph theory and a powerful tool in various computational applications.