Definition

Floyd-Warshall computes shortest paths between all pairs of vertices at once. It considers each vertex as a potential intermediate point to find shorter paths.

Key Characteristics

• ✓All-Pairs Shortest Path: Computes shortest distances for all (i, j) pairs in one run.
• ✓Dynamic Programming: Uses recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
• ✓Negative Weights OK: Can handle negative edges if no negative cycles exist.

Time Complexity