Floyd-Warshall algorithm in Data Structures Theory - Time & Space Complexity

Time Complexity: Floyd-Warshall algorithm

O(n³)

Understanding Time Complexity

We want to understand how the Floyd-Warshall algorithm's running time changes as the graph size grows.

Specifically, how does the number of steps increase when we add more nodes?

Scenario Under Consideration

Analyze the time complexity of the Floyd-Warshall algorithm below.

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    

This code updates the shortest paths between all pairs of nodes by considering each node as an intermediate step.

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 n times, so the inner update runs n x n x n = n³ times.

How Execution Grows With Input

As the number of nodes n grows, the steps increase by roughly the cube of n.

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

Pattern observation: If you double the number of nodes, the work grows eight times (2³ = 8).

Final Time Complexity

Time Complexity: O(n³)

This means the time needed grows very quickly as the graph gets bigger, roughly proportional to the cube of the number of nodes.

Common Mistake

[X] Wrong: "Since there are three loops, the algorithm must be O(n) because loops run one after another."

[OK] Correct: The loops are nested inside each other, so the total steps multiply, not add. This makes the time grow much faster than just n.

Interview Connect

Understanding Floyd-Warshall's time complexity helps you explain why it works well for small graphs but can be slow for large ones, showing your grasp of algorithm efficiency.

Self-Check

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

Practice

1. What is the main purpose of the Floyd-Warshall algorithm in graph theory?

easy

A. To perform depth-first search

B. To find the minimum spanning tree

C. To detect cycles in a graph

D. To find shortest paths between all pairs of vertices

Solution

1. Step 1: Understand the algorithm's goal

   The Floyd-Warshall algorithm is designed to find the shortest paths between every pair of vertices in a graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices, cycle detection finds cycles, and DFS explores nodes, none of which match Floyd-Warshall's purpose.

3. Final Answer:

   To find shortest paths between all pairs of vertices -> Option D

4. Quick Check:

   Floyd-Warshall = All pairs shortest paths [OK]

Hint: Remember: Floyd-Warshall finds shortest paths between all pairs [OK]

Common Mistakes:

• Confusing it with minimum spanning tree algorithms
• Thinking it finds shortest path from one source only
• Mixing it up with cycle detection methods

2. Which of the following correctly represents the core update step in the Floyd-Warshall algorithm for vertices i, j, and k?

easy

A. dist[i][j] = dist[i][k] * dist[k][j]

B. dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])

C. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

D. dist[i][j] = dist[i][j] + dist[k][k]

Solution

1. Step 1: Recall the update formula

   The Floyd-Warshall algorithm updates the shortest distance between i and j by checking if going through k is shorter.

2. Step 2: Identify the correct mathematical operation

   The update uses the minimum of the current distance and the sum of distances through k, which matches dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

3. Final Answer:

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) -> Option C

4. Quick Check:

   Update step uses min sum of paths [OK]

Hint: Update distances using minimum sum through intermediate vertex [OK]

Common Mistakes:

• Using max instead of min
• Multiplying distances instead of adding
• Adding distances incorrectly without min

3. Given the following distance matrix for a graph with vertices 0, 1, 2:

dist = [[0, 3, 999],
        [2, 0, 5],
        [999, 1, 0]]

After running one iteration of Floyd-Warshall with intermediate vertex k=1, what is the updated distance from vertex 0 to vertex 2?

medium

A. 8

B. 5

C. 999

D. 3

Solution

1. Step 1: Identify current distances

   dist[0][2] = 999 (no direct path), dist[0][1] = 3, dist[1][2] = 5.

2. Step 2: Calculate new distance via vertex 1

   New distance = dist[0][1] + dist[1][2] = 3 + 5 = 8, which is less than 999, so update dist[0][2] to 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Updated dist[0][2] = 3 + 5 = 8 [OK]

Hint: Add distances through k and compare with current [OK]

Common Mistakes:

• Not updating because original was 999
• Using dist[0][2] directly without checking intermediate
• Mixing vertex indices

4. Consider this incorrect Floyd-Warshall update step:

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[j][k]:
                dist[i][j] = dist[i][k] + dist[j][k]

What is the main error in this code?

medium

A. The condition uses dist[j][k] instead of dist[k][j]

B. The loops should be reversed in order

C. The update should use max instead of min

D. The code misses initialization of dist matrix

Solution

1. Step 1: Analyze the update condition

   The code compares dist[i][j] with dist[i][k] + dist[j][k], but the second term should be dist[k][j] to represent path i->k->j.

2. Step 2: Identify the correct indexing

   Using dist[j][k] reverses the direction and gives wrong path length, causing incorrect updates.

3. Final Answer:

   The condition uses dist[j][k] instead of dist[k][j] -> Option A

4. Quick Check:

   Correct indexing is dist[k][j] in update [OK]

Hint: Check order of indices in sum: dist[i][k] + dist[k][j] [OK]

Common Mistakes:

• Swapping indices in distance matrix
• Changing loop order unnecessarily
• Confusing min with max in update

5. You have a graph with 4 vertices and the following edges with weights:

(0 -> 1) = 4
(0 -> 2) = 11
(1 -> 2) = -3
(2 -> 3) = 2
(3 -> 1) = 1

Using Floyd-Warshall, what is the shortest distance from vertex 0 to vertex 3 after all iterations?

hard

A. 9

B. 3

C. 6

D. 8

Solution

1. Step 1: Identify possible paths from 0 to 3

   Paths include:
   - 0->1->2->3
   - 0->2->3 directly

2. Step 2: Calculate path distances

   0->1 = 4
   1->2 = -3
   2->3 = 2
   Sum for 0->1->2->3 = 4 + (-3) + 2 = 3
   0->2 = 11
   0->2->3 = 11 + 2 = 13
   Also check 0->1->2->3->1->2->3 cycles but no negative cycle exists.

3. Step 3: Check if going through 3->1->2 improves path

   3->1 = 1, 1->2 = -3, so cycle 1->2->3->1 has total weight 0, no negative cycle.

4. Step 4: Final shortest distance

   Shortest distance from 0 to 3 is 3.

5. Final Answer:

   3 -> Option B

6. Quick Check:

   Shortest distance from 0 to 3 = 4 + (-3) + 2 = 3 [OK]

Hint: Sum edge weights along shortest path carefully [OK]

Common Mistakes:

• Ignoring negative edge weights
• Assuming direct path is shortest
• Not considering cycles properly