# Floyd–Warshall — All-Pairs Shortest Paths (C++) ## Summary Floyd–Warshall computes shortest paths between every pair of vertices using dynamic programming. It is simple and handles negative weights (but not negative cycles). ## Algorithm Let `d[i][j]` be shortest distance from `i` to `j`. Initialize with direct edge weights (or `∞` if no edge). Update: ```cpp\nfor (k = 0..n-1) for (i = 0..n-1) for (j = 0..n-1) d[i][j]= min(d[i][j], d[i][k]+ d[k][j]);\n``` ## Complexity - Time: **O(n^3)** - Space: **O(n^2)** ## Repo notes See `floyed_warshall.cpp` in the repository: `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/floyed_warshall.cpp`. The implementation includes a `path` matrix for reconstructing paths. ## When to use - Use for dense graphs or when `n` is small to moderate and you need all-pairs results. ## Pitfalls - O(n^3) becomes infeasible for large `n` (e.g., n>1000). Prefer Johnson's algorithm for sparse graphs. ## Source `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/floyed_warshall.cpp`.