Quiz: When to Use Floyd-Warshall

You have a graph with $500$ vertices and $1{,}000$ edges, and you need shortest paths between all pairs. You consider Floyd-Warshall ($O(V^3)$) and running Dijkstra from every vertex ($O(V \cdot (V + E) \log V)$). Which is faster here?

1. A.Dijkstra from every vertex, because the graph is sparse. $500 \times 1{,}500 \times \log(500) \approx 6.75 \times 10^6$ operations beats $500^3 = 1.25 \times 10^8$
2. B.They are the same because $V = 500$
3. C.Floyd-Warshall, because its simpler constant factors outweigh the higher operation count
4. D.Neither works. You need Johnson's Algorithm