Algorithms and Data Structures · Senior · Question 4 of 75
What is the complexity of Floyd-Warshall, and when is it a reasonable choice?
- 1O(V log V); for single-source paths on huge graphs
- ✓Correct answer: O(V³); for all-pairs shortest paths on small, dense graphs
- 3O(E); for checking whether a graph is connected
Explanation
It's three nested loops over vertices, updating dist[i][j] through every intermediate k. Simple and handles negative edges (without negative cycles), but at V = 10,000 it's already 10¹² steps.