Cubic complexity means the work grows on the scale of the input size cubed. In Floyd–Warshall, three nested loops check every combination of intermediate, starting, and destination vertices, giving O(V³) time for V vertices. The algorithm stores a V × V distance matrix, using O(V²) space. section 9.1
Counting the loops
For a graph with four vertices, the algorithm tests each vertex as a bridge for every start-and-destination pair. It proceeds through bridge vertices in phases, updating the distance matrix as it finds cheaper routes. section 9.1
Listing 9.1 Pseudocode for Floyd Warshall algorithm
Define infinity as a value larger than any possible path distance.
Initialize a 2D array distance_matrix matching the dimensions of the input graph.
For each row i and column j in the graph:
If there is a direct edge from i to j, distance_matrix[i][j] = edge_weight
If i equals j, distance_matrix[i][j] = 0
Else, distance_matrix[i][j] = infinity
For every vertex k (acting as the intermediate bridge):
For every vertex i (acting as the start node):
For every vertex j (acting as the destination node):
If distance_matrix[i][k] + distance_matrix[k][j] < distance_matrix[i][j]:
Update distance_matrix[i][j] to the new cheaper sum
Return distance_matrix
Follow the three nested loops that account for the algorithm’s cubic running time. section 9.1
