What is the Floyd-Warshall algorithm?

The Floyd-Warshall algorithm is a dynamic programming algorithm for finding the shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices.

What is the time complexity of the Floyd-Warshall algorithm?

The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices in the graph. This makes it suitable for dense graphs.

Dynamic Programming

Floyd-Warshall Algorithm

The classic dynamic programming solution for finding the shortest paths between all pairs of vertices in a graph.

Floyd-Warshall Implementation

This implementation initializes a distance matrix and iteratively considers each vertex as an intermediate point in the shortest paths.

                            function floydWarshall(graph) {
                            const dist = graph;
                            const V = graph.length;
                            
                            for (let k = 0; k < V; k++) {
                            for (let i = 0; i < V; i++) {
                            for (let j = 0; j < V; j++) {
                            if (dist[i][k] + dist[k][j] < dist[i][j]) {
                            dist[i][j] = dist[i][k] + dist[k][j];
                            }
                            }
                            }
                            }
                            
                            return dist;
                            }
                        

AI Coach Hint: The core idea of Floyd-Warshall is surprisingly simple: for every pair of vertices (i, j), what is the shortest path from i to j? It tries to improve this path by considering if going through an intermediate vertex `k` would be shorter. It does this for all possible intermediate vertices `k`.