An all-pairs shortest path algorithm that finds the shortest distance between every pair of vertices.
The Floyd-Warshall algorithm is a dynamic programming algorithm used to solve the all-pairs shortest path problem. Unlike single-source algorithms like Dijkstra's and Bellman-Ford, it computes the shortest paths between all pairs of vertices in a single execution. The algorithm works by considering all possible intermediate vertices for each pair of start and end nodes. It iteratively builds up the solution by allowing an increasing subset of vertices to be used as intermediaries. It initializes a distance matrix `dist[i][j]` with the direct edge weight between `i` and `j` (or infinity if no direct edge exists). Then, for each vertex `k` from 1 to `V`, it updates the shortest path between every pair of vertices `(i, j)` by checking if the path from `i` to `j` via `k` (i.e., `dist[i][k] + dist[k][j]`) is shorter than the currently known path `dist[i][j]`. After iterating through all possible intermediate vertices `k`, the matrix `dist` will contain the shortest path distances between every pair of vertices. The algorithm has a time complexity of O(V^3), making it suitable for dense graphs but less so for large, sparse graphs. Like Bellman-Ford, it can handle negative edge weights and can be used to detect negative cycles.