Floyd-Warshall vs Johnson's Algorithm

Johnson's algorithm solves all-pairs shortest paths in $O(n^2 \log n + nm)$ time using Bellman-Ford once and Dijkstra $n$ times. For sparse graphs ($m \ll n^2$), Johnson's is faster than Floyd-Warshall's $O(n^3)$.

For dense graphs or when simplicity matters, Floyd-Warshall is preferred. It also has better constants and is easier to implement. In a contest, I reach for Floyd-Warshall first if $n \leq 500$.

Space complexity is $O(n^2)$ for the data structures used.