Shortest Routes II gives you queries for shortest paths. If is large, running Dijkstra for each query is too slow.
Instead, run Floyd-Warshall once in to precompute all distances. Then answer each query in by indexing the array. Total time: . This beats when is large. The pattern is: expensive preprocessing, cheap queries. Recognize this pattern and you will know when to use Floyd-Warshall.
Space complexity is for the data structures used.