Auxiliary Space Complexity of Floyd Warshall Algorithm
The auxiliary space complexity of the Floyd-Warshall algorithm is O(V2), where V is the number of vertices in the graph. To create a 2-D matrix in order to store the shortest distance for each pair of nodes.
Distance Matrix: Utilizes a 2D array to store shortest distances between all pairs of vertices.
- Matrix size: V x V, where V is the number of vertices.
- Each entry represents the shortest distance between two vertices.
- Space complexity: O(V2).
Additional Variables: May require supplementary variables for iteration and calculation.
- Space occupied by these variables is typically minimal compared to the distance matrix.
- Doesn’t significantly affect overall space complexity.
Time and Space Complexity of Floyd Warshall Algorithm
The Floyd Warshall Algorithm has a time complexity of O(V3) and a space complexity of O(V2), where V represents the number of vertices in the graph. This algorithm computes the shortest paths between all pairs of vertices in a weighted graph. The time complexity arises from the triple nested loops used to update the shortest path matrix, while the space complexity is determined by the need to store the distances between all pairs of vertices in a 2D array.
| Aspect | Complexity |
|---|---|
| Time Complexity | O(V3) |
| Space Complexity | O(V2) |
Let’s explore the detailed time and space complexity of the Floyd Warshall Algorithm:
Contact Us