Floyd Warshall All Pairs Shortest Path in DSA Python - Execution Trace

Concept Flow - Floyd Warshall All Pairs Shortest Path

Start with distance matrix

↓

Pick intermediate node k

↓

For each pair (i, j):

↓

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

Yes/No↓

Update dist[i

↓

Repeat for all i, j

↓

Repeat for all k

↓

Final shortest paths matrix

The algorithm updates shortest paths by considering each node as an intermediate step, improving distances if a shorter path is found through that node.

Execution Sample

DSA Python

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 runs Floyd Warshall on a 4-node graph to find shortest paths between all pairs.

Execution Table

Step	Operation	Intermediate Node k	Pair (i,j)	Old dist[i][j]	New dist[i][j]	Updated?	Distance Matrix State
1	Initialize	-	-	-	-	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
2	Check i=0,j=2 via k=0	0	(0,2)	∞	0+∞=∞	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
3	Check i=1,j=3 via k=0	0	(1,3)	∞	8+7=15	Yes	[[0,3,∞,7],[8,0,2,15],[5,∞,0,1],[2,∞,∞,0]]
4	Check i=2,j=1 via k=0	0	(2,1)	∞	5+3=8	Yes	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,∞,∞,0]]
5	Check i=3,j=1 via k=0	0	(3,1)	∞	2+3=5	Yes	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
6	Check i=3,j=2 via k=0	0	(3,2)	∞	2+∞=∞	No	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]
7	Check i=0,j=2 via k=1	1	(0,2)	∞	3+2=5	Yes	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
8	Check i=3,j=2 via k=1	1	(3,2)	∞	5+2=7	Yes	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
9	Check i=1,j=3 via k=2	2	(1,3)	15	2+1=3	Yes	[[0,3,5,7],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
10	Check i=0,j=3 via k=2	2	(0,3)	7	5+1=6	Yes	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
11	Check i=3,j=0 via k=3	3	(3,0)	2	0+2=2	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
12	Check i=1,j=0 via k=3	3	(1,0)	8	3+2=5	Yes	[[0,3,5,6],[5,0,2,3],[5,8,0,1],[2,5,7,0]]
13	Check i=2,j=0 via k=3	3	(2,0)	5	1+2=3	Yes	[[0,3,5,6],[5,0,2,3],[3,8,0,1],[2,5,7,0]]
14	Check i=2,j=1 via k=3	3	(2,1)	8	1+5=6	Yes	[[0,3,5,6],[5,0,2,3],[3,6,0,1],[2,5,7,0]]
15	Check i=3,j=1 via k=3	3	(3,1)	5	0+5=5	No	[[0,3,5,6],[5,0,2,3],[3,6,0,1],[2,5,7,0]]
16	End	-	-	-	-	No	[[0,3,5,6],[5,0,2,3],[3,6,0,1],[2,5,7,0]]

💡 All intermediate nodes k processed; no further updates possible.

Variable Tracker

Variable	Start	After k=0	After k=1	After k=2	After k=3	Final
dist	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,5,∞,0]]	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]	[[0,3,5,6],[5,0,2,3],[3,6,0,1],[2,5,7,0]]	[[0,3,5,6],[5,0,2,3],[3,6,0,1],[2,5,7,0]]

Key Moments - 3 Insights

Why do we check if dist[i][k] + dist[k][j] < dist[i][j] instead of just updating dist[i][j]?

Because we only update dist[i][j] if going through node k gives a shorter path. This is shown in execution_table rows like 3 and 7 where updates happen only when the new path is shorter.

What does the intermediate node k represent in the algorithm?

It represents the node we are currently allowing as a possible stopover between i and j. The algorithm tries to improve paths by including k, as seen in the stepwise updates in the execution_table.

Why does the distance matrix start with some distances as infinity (∞)?

Infinity means no direct edge between those nodes initially. The algorithm tries to find shorter paths by combining edges, replacing ∞ with actual distances if found, as in rows 3,4,5.

Visual Quiz - 3 Questions

Look at the execution_table at step 7. What is the new distance from node 0 to node 2 after considering intermediate node k=1?

A ∞

B 5

C 3

D 7

💡 Hint

Check the 'New dist[i][j]' column at step 7 for pair (0,2).

At which intermediate node k does the distance from node 1 to node 3 first update to 3?

A k=2

B k=1

C k=0

D k=3

💡 Hint

Look at the 'Intermediate Node k' and 'New dist[i][j]' columns for pair (1,3) in execution_table.

If the initial distance from node 3 to node 1 was not ∞ but 4, how would the distance matrix change after k=0?

A It would remain the same as in step 5.

B It would update to 5 as in step 5.

C It would update to 4 immediately at initialization.

D It would update to 7 after k=1.

💡 Hint

Check the initial 'Start' state in variable_tracker for dist[3][1].

Concept Snapshot

Floyd Warshall Algorithm:
- Uses dynamic programming to find shortest paths between all pairs.
- Iterates over all nodes as intermediate points (k).
- Updates dist[i][j] if dist[i][k] + dist[k][j] < dist[i][j].
- Handles graphs with positive or zero edge weights.
- Time complexity: O(n³) for n nodes.
- Result: shortest distance matrix between all pairs.

Full Transcript

Floyd Warshall algorithm finds shortest paths between all pairs of nodes in a graph. It starts with a distance matrix where direct edges have their weights and no edges are marked as infinity. The algorithm picks each node as an intermediate node k and tries to improve the distance between every pair (i,j) by checking if going through k is shorter. If yes, it updates the distance. This process repeats for all nodes k. The final matrix shows the shortest distances between all pairs. Key points include checking if the new path is shorter before updating and understanding that infinity means no direct edge initially. The algorithm runs in cubic time and works for graphs with positive weights.

Practice

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

easy

A. To find the shortest paths between all pairs of vertices in a weighted graph

B. To find the minimum spanning tree of a graph

C. To perform a depth-first search traversal

D. To detect cycles in a graph

Solution

1. Step 1: Understand Floyd Warshall's goal

   The Floyd Warshall algorithm calculates shortest paths between every pair of vertices in a weighted graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree, DFS, and cycle detection serve different purposes than Floyd Warshall.

3. Final Answer:

   To find the shortest paths between all pairs of vertices in a weighted graph -> Option A

4. Quick Check:

   Floyd Warshall = all pairs shortest paths [OK]

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

Common Mistakes:

• Confusing with minimum spanning tree algorithms
• Thinking it finds shortest path from one source only
• Mixing with traversal algorithms like DFS or BFS

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in Python for a graph with n vertices?

easy

A. dist = [[0] * n] * n

B. dist = [[float('inf')] * n for _ in range(n)]

C. dist = [float('inf')] * n * n

D. dist = [0 for _ in range(n)]

Solution

1. Step 1: Understand matrix initialization

   We need a 2D list with size n x n, each element set to infinity initially.

2. Step 2: Check each option

   dist = [[float('inf')] * n for _ in range(n)] correctly creates a new list for each row with float('inf'). dist = [float('inf')] * n * n creates a 1D list, not 2D. dist = [[0] * n] * n creates shallow copies causing aliasing. dist = [0 for _ in range(n)] creates 1D list.

3. Final Answer:

   dist = [[float('inf')] * n for _ in range(n)] -> Option B

4. Quick Check:

   2D list with inf values = dist = [[float('inf')] * n for _ in range(n)] [OK]

Hint: Use list comprehension for 2D matrix initialization [OK]

Common Mistakes:

• Using multiplication for 2D lists causing shared references
• Creating 1D list instead of 2D
• Initializing with zeros instead of infinity

3. What will be the output distance matrix after running Floyd Warshall on this graph represented by adjacency matrix?

graph = [
  [0, 3, float('inf'), 7],
  [8, 0, 2, float('inf')],
  [5, float('inf'), 0, 1],
  [2, float('inf'), float('inf'), 0]
]

medium

A. [[0, 3, 5, 6], [5, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]]

B. [[0, 3, 10, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, 5, 7, 0]]

C. [[0, 3, 7, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, 5, 7, 0]]

D. [[0, 3, 5, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, 5, 7, 0]]

Solution

1. Step 1: Initialize dist matrix same as graph

   Start with dist = graph matrix, where float('inf') means no direct edge.

2. Step 2: Update distances using Floyd Warshall logic

   Iterate k from 0 to 3, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for all i,j. After all iterations, shortest paths are computed.

3. Final Answer:

   [[0, 3, 5, 6], [5, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]] -> Option A

4. Quick Check:

   All pairs shortest paths matrix = [[0, 3, 5, 6], [5, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]] [OK]

Hint: Update dist with min of current and via intermediate vertex [OK]

Common Mistakes:

• Not updating distances through intermediate vertices
• Confusing indices in nested loops
• Leaving float('inf') where shorter paths exist

4. Consider this snippet of Floyd Warshall implementation in Python:

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

What is the main bug if dist[i][k] or dist[k][j] is float('inf')?

medium

A. It causes incorrect updates because adding infinity is not handled

B. It causes incorrect addition leading to overflow errors

C. No bug, the code works fine with infinity values

D. It causes syntax errors due to float('inf') usage

Solution

1. Step 1: Understand addition with infinity in Python

   float('inf') + any finite number = float('inf'), and float('inf') + float('inf') = float('inf').

2. Step 2: Check the condition

   The condition if dist[i][k] + dist[k][j] < dist[i][j] will be False whenever the sum is inf, because inf is not less than any finite or inf value. Thus, no incorrect updates occur; invalid paths are correctly skipped.

3. Final Answer:

   No bug, the code works fine with infinity values -> Option C

4. Quick Check:

   inf + x = inf, inf < y always False for path updates [OK]

Hint: Python's float('inf') handles additions and comparisons correctly for FW [OK]

Common Mistakes:

• Believing inf causes incorrect updates
• Confusing with integer overflow issues
• Thinking syntax error with inf

5. Given a graph with negative edge weights but no negative cycles, how does Floyd Warshall algorithm handle these edges to find shortest paths?

hard

A. It requires a separate algorithm to preprocess negative edges before running

B. It fails because it cannot handle negative weights at all

C. It ignores negative edges and only uses positive weights

D. It updates distances by considering intermediate vertices, correctly handling negative edges without cycles

Solution

1. Step 1: Understand Floyd Warshall with negative edges

   The algorithm can handle negative edges by updating distances through intermediate vertices, as long as no negative cycles exist.

2. Step 2: Confirm no negative cycle condition

   If negative cycles exist, shortest paths are undefined. Without them, Floyd Warshall converges to correct shortest paths.

3. Final Answer:

   It updates distances by considering intermediate vertices, correctly handling negative edges without cycles -> Option D

4. Quick Check:

   Negative edges allowed if no negative cycles [OK]

Hint: Floyd Warshall handles negative edges if no negative cycles exist [OK]

Common Mistakes:

• Thinking Floyd Warshall cannot handle any negative edges
• Confusing negative edges with negative cycles
• Assuming preprocessing is always needed