Floyd-Warshall algorithm in Data Structures Theory - Step-by-Step Execution

Concept Flow - Floyd-Warshall algorithm

Start with distance matrix

↓

For each intermediate vertex k

↓

For each source vertex i

↓

For each destination vertex j

↓

Check if path i->k + k->j < i->j

Yes No↓

Update distance i->j

↓

Repeat for all i,j,k

↓

Final shortest paths matrix

The algorithm updates shortest paths by considering each vertex as an intermediate stop, improving distances step-by-step.

Execution Sample

Data Structures Theory

INF = float('inf')
dist = [[0, 3, INF, 7],
        [8, 0, 2, INF],
        [5, INF, 0, 1],
        [2, INF, INF, 0]]
for k in range(4):
  for i in range(4):
    for j in range(4):
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

This code updates the distance matrix to find shortest paths between all pairs of vertices.

Analysis Table

Step	k (intermediate)	i (source)	j (destination)	Condition: dist[i][k] + dist[k][j] < dist[i][j]	Action	Updated dist[i][j]
1	0	1	2	dist[1][0] + dist[0][2] = 8 + INF = INF < 2? No	No update	2
2	0	1	3	dist[1][0] + dist[0][3] = 8 + 7 = 15 < INF? Yes	Update dist[1][3]	15
3	0	2	1	dist[2][0] + dist[0][1] = 5 + 3 = 8 < INF? Yes	Update dist[2][1]	8
4	0	3	1	dist[3][0] + dist[0][1] = 2 + 3 = 5 < INF? Yes	Update dist[3][1]	5
5	1	0	2	dist[0][1] + dist[1][2] = 3 + 2 = 5 < INF? Yes	Update dist[0][2]	5
6	1	0	3	dist[0][1] + dist[1][3] = 3 + 15 = 18 < 7? No	No update	7
7	1	3	2	dist[3][1] + dist[1][2] = 5 + 2 = 7 < INF? Yes	Update dist[3][2]	7
8	2	0	3	dist[0][2] + dist[2][3] = 5 + 1 = 6 < 7? Yes	Update dist[0][3]	6
9	2	1	3	dist[1][2] + dist[2][3] = 2 + 1 = 3 < 15? Yes	Update dist[1][3]	3
10	3	1	0	dist[1][3] + dist[3][0] = 3 + 2 = 5 < 8? Yes	Update dist[1][0]	5
11	3	2	0	dist[2][3] + dist[3][0] = 1 + 2 = 3 < 5? Yes	Update dist[2][0]	3
12	3	2	1	dist[2][3] + dist[3][1] = 1 + 5 = 6 < 8? Yes	Update dist[2][1]	6
13	3	3	2	dist[3][3] + dist[3][2] = 0 + 7 = 7 < 7? No	No update	7
14	3	3	3	dist[3][3] + dist[3][3] = 0 + 0 = 0 < 0? No	No update	0

💡 All pairs checked for all intermediate vertices k=0 to 3; no further updates possible.

State Tracker

Variable	Start	After k=0	After k=1	After k=2	After k=3 (Final)
dist[0][3]	7	7	7	6	6
dist[1][3]	INF	15	15	3	3
dist[2][1]	INF	8	8	8	6
dist[3][1]	INF	5	5	5	5
dist[3][2]	INF	INF	7	7	7
dist[1][0]	8	8	8	8	5
dist[2][0]	5	5	5	5	3

Key Insights - 3 Insights

Why do we check if dist[i][k] + dist[k][j] < dist[i][j]?

Because we want to see if going through vertex k gives a shorter path from i to j than the current known path. This is shown in execution_table rows like 2 and 5 where updates happen only if the new path is shorter.

Why do we need three nested loops over k, i, and j?

The outer loop k tries each vertex as an intermediate point. The inner loops i and j check all pairs of start and end vertices to update distances. This ensures all possible paths through any vertex are considered, as seen in the stepwise updates in execution_table.

What does INF represent and why is it important?

INF means no direct path between two vertices initially. It helps identify unreachable paths. The algorithm updates INF to a real distance if a shorter path is found, as shown in rows where INF changes to a number.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the updated distance from vertex 0 to 2?

A 2

B 5

C INF

D 3

💡 Hint

Check the 'Updated dist[i][j]' column at step 5 where i=0, j=2.

At which iteration does the distance from vertex 1 to 3 first get updated to a value less than INF?

A Step 14

B Step 9

C Step 2

D Step 5

💡 Hint

Look at the 'Action' and 'Updated dist[i][j]' columns for i=1, j=3 in execution_table.

If the initial distance from vertex 3 to 2 was not INF but 10, how would the update at step 7 change?

A Update would still occur, changing distance to 7

B No update would occur because 5 + 2 = 7 is less than 10

C Update would not occur because 7 is not less than 10

D Distance would become INF

💡 Hint

Check step 7 where dist[3][1] + dist[1][2] = 5 + 2 = 7 and compare with initial distance.

Concept Snapshot

Floyd-Warshall algorithm finds shortest paths between all pairs of vertices.
Uses a distance matrix updated by considering each vertex as an intermediate point.
Three nested loops: k (intermediate), i (source), j (destination).
Update rule: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
Handles negative edges but no negative cycles.
Final matrix shows shortest distances between all pairs.

Full Transcript

The Floyd-Warshall algorithm starts with a matrix of distances between vertices, where direct edges have their weights and no edges are marked as infinity. It uses three nested loops: the outer loop picks each vertex as an intermediate point, and the inner loops check all pairs of source and destination vertices. For each pair, it checks if going through the intermediate vertex offers a shorter path. If yes, it updates the distance. This process repeats for all vertices, gradually improving the shortest path estimates. The final matrix after all iterations contains the shortest distances between every pair of vertices. This method works even with negative edge weights but assumes no negative cycles exist. The execution table shows step-by-step updates, and the variable tracker follows key distance values as they change. Key moments clarify why the update condition is checked, why three loops are needed, and the role of infinity in representing unreachable paths.

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