Why is Floyd-Warshall O even when the graph has relatively…
1 reactions
Why is Floyd-Warshall O even when the graph has relatively few edges?
I'm trying to understand the reasoning behind the O(V³) complexity of Floyd-Warshall rather than just memorizing it.
Since the algorithm considers every intermediate vertex, is the simplest way to think about the complexity as three nested iterations over the vertices?
I'm particularly interested in the theoretical reasoning behind the complexity.
#technology
I'm trying to understand the reasoning behind the O(V³) complexity of Floyd-Warshall rather than just memorizing it.
Since the algorithm considers every intermediate vertex, is the simplest way to think about the complexity as three nested iterations over the vertices?
I'm particularly interested in the theoretical reasoning behind the complexity.
#technology
1
| 5,000 mlx | |
| 8 | |
| 1 |