The Floyd–Warshall algorithm is a popular method for solving the All-Pair…

For an algorithm built from nested loops where each iteration does constant work, the time complexity is the product of the ranges of the independent loop variables: one loop over n items gives O(n), two independent nested loops each ranging over n give O(n²), and three independent nested loops each ranging over n give O(n³).

The Floyd–Warshall algorithm computes the shortest distance between every pair of vertices using dynamic programming over an intermediate vertex. For a graph with n vertices, it uses three independent nested loops:

1. An outer loop over the intermediate vertex k, running from 1 to n.

2. A middle loop over the source vertex i, running from 1 to n for each value of k.

3. An inner loop over the destination vertex j, running from 1 to n for each value of i.

4. Inside the innermost loop, the constant-time update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) is performed.

Since k, i, and j each independently range over all n vertices and the innermost step is O(1), the total number of operations is n × n × n = n³, so the running time is Θ(n³).

This matches the standard analysis given in MIT OpenCourseWare's Introduction to Algorithms (Lecture 19, All-Pairs Shortest Paths) and the NIST Dictionary of Algorithms and Data Structures, and it distinguishes Floyd–Warshall from a single nested-pair pass over an adjacency matrix (which is O(n²)).

Therefore, the time complexity of the Floyd–Warshall algorithm for a graph with n vertices is O(n³).