Floyd Warshall All Pairs Shortest Path in DSA Typescript - Time & Space Complexity

Time Complexity: Floyd Warshall All Pairs Shortest Path

O(n³)

Understanding Time Complexity

We want to understand how the time needed to find shortest paths between all pairs of points grows as the number of points increases.

How does the running time change when the graph size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function floydWarshall(graph: number[][]): number[][] {
  const dist = graph.map(row => row.slice());
  const n = graph.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}
    

This code finds the shortest distances between every pair of points in a graph using three nested loops.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The triple nested loops that update distances.
• How many times: Each loop runs from 0 to n-1, so the innermost operation runs about n x n x n = n³ times.

How Execution Grows With Input

As the number of points (n) grows, the number of operations grows very fast because every pair of points is checked for every possible intermediate point.

Input Size (n)	Approx. Operations
10	1,000
100	1,000,000
1000	1,000,000,000

Pattern observation: When n increases ten times, operations increase about a thousand times (n³ growth).

Final Time Complexity

Time Complexity: O(n³)

This means the time needed grows very quickly as the graph size grows, roughly proportional to the cube of the number of points.

Common Mistake

[X] Wrong: "Since there are three loops, the time complexity is O(n) because loops run one after another."

[OK] Correct: The loops are nested, not sequential, so the total operations multiply, making it O(n³), not just O(n).

Interview Connect

Understanding this algorithm's time complexity helps you explain how nested loops affect performance and why some algorithms are slower on bigger inputs. This skill is valuable for solving real problems efficiently.

Self-Check

"What if we replaced the triple nested loops with a recursive approach that splits the graph? How might that affect the time complexity?"