Explain Floyd-Warshall algorithm and its applications.

Floyd-Warshall finds shortest paths between all pairs of vertices, handling negative edges (but not negative cycles). Uses DP: dist[i][j][k] = shortest path from i to j using only first k vertices as intermediates. Recurrence: min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]). Time O(V^3), space O(V^2). Detects negative cycles when diagonal becomes negative. Used in network routing, transitive closure.