Floyd Warshall All Pairs Shortest Path in DSA C++ - 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->j is shorter

↓

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 point, checking if going through it shortens the path between every pair of nodes.

Execution Sample

DSA C++

int dist[V][V] = {
  {0, 3, INF, 7},
  {8, 0, 2, INF},
  {5, INF, 0, 1},
  {2, INF, INF, 0}
};

Initialize distance matrix with direct edge weights; INF means no direct edge.

Execution Table

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

💡 All intermediate nodes k processed; shortest paths finalized.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 8	After Step 11	Final
dist[2][1]	∞	8	8	8	8	6	6
dist[3][1]	∞	∞	5	5	5	5	5
dist[0][2]	∞	∞	∞	5	5	5	5
dist[3][2]	∞	∞	∞	7	7	7	7
dist[0][3]	7	7	7	7	6	6	6
dist[1][3]	∞	∞	∞	∞	3	3	3
dist[1][0]	8	8	8	8	8	5	5
dist[2][0]	5	5	5	5	5	3	3

Key Moments - 3 Insights

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

Because we want to see if going through node k gives a shorter path from i to j than the current known path. This is shown in execution_table rows 2-12 where updates happen only if this condition is true.

Why do we repeat the process for every node k as intermediate?

Each node k might help find shorter paths between pairs (i, j) that were not direct or shorter before. The algorithm ensures all possible intermediate nodes are considered, as seen in the execution_table where k changes from 0 to 3.

What does INF mean and how does it affect updates?

INF means no direct edge between nodes. When adding distances, if one part is INF, the sum is considered INF (no path). Updates only happen if a real shorter path is found, preventing invalid paths, as seen in steps where no update occurs due to INF.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the new distance dist[2][1]?

A 8

B ∞

C 5

D 2

💡 Hint

Check the 'New dist[i][j]' column for step 3 in execution_table.

At which intermediate node k does dist[0][3] get updated to 6?

A k=1

B k=2

C k=3

D k=0

💡 Hint

Look at execution_table step 7 where dist[0][3] changes from 7 to 6.

If the initial dist[1][3] was 4 instead of INF, how would the final dist[1][3] change?

A It would be 7

B It would be 4

C It would remain 3

D It would be INF

💡 Hint

Check how updates happen in execution_table steps 8 and 11; shorter paths overwrite longer ones.

Concept Snapshot

Floyd Warshall Algorithm:
- Uses a distance matrix dist[][]
- Iterates over all nodes k as intermediate
- Updates dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- Finds shortest paths between all pairs
- Handles negative edges but no negative cycles
- Time complexity: O(V^3)

Full Transcript

Floyd Warshall algorithm finds shortest paths between all pairs of nodes in a graph. It starts with a distance matrix showing direct edges or infinity if no direct edge exists. Then, for each node k, it checks if using k as an intermediate node shortens the path between every pair (i, j). If yes, it updates the distance. This process repeats for all nodes k, ensuring all possible intermediate paths are considered. The final matrix shows the shortest distances between all pairs. The key is comparing current distances with new possible paths through k and updating only if shorter. Infinity means no path, so sums involving infinity remain infinite. The algorithm runs in cubic time relative to the number of nodes.

Practice

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

easy

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

B. To find the minimum spanning tree of a graph

C. To detect cycles in a directed graph

D. To perform depth-first search traversal

Solution

1. Step 1: Understand Floyd Warshall algorithm goal

   The Floyd Warshall algorithm is designed to find shortest paths between every pair of vertices in a weighted graph, including negative weights but no negative cycles.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total edge weight, cycle detection algorithms find cycles, and DFS is a traversal method. These are different from Floyd Warshall's goal.

3. Final Answer:

   To find 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 Floyd Warshall with minimum spanning tree algorithms
• Thinking it only finds shortest path from one source
• Assuming it detects cycles instead of paths

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

easy

A. for (int i = 0; i < n; i++) dist[i] = graph[i];

B. for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j];

C. dist = graph;

D. dist = new int[n][n];

Solution

1. Step 1: Understand distance matrix initialization

   We need to copy each element from the adjacency matrix graph to dist element-wise because dist is a 2D array and direct assignment is not allowed in C++.

2. Step 2: Analyze each option

   for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; uses nested loops to copy each element correctly. for (int i = 0; i < n; i++) dist[i] = graph[i]; tries to assign a row pointer which is invalid for 2D arrays. dist = graph; tries direct assignment which is invalid for arrays. dist = new int[n][n]; only allocates memory but does not initialize values.

3. Final Answer:

   for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; -> Option B

4. Quick Check:

   Element-wise copy needed = for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = graph[i][j]; [OK]

Hint: Use nested loops to copy 2D arrays element-wise [OK]

Common Mistakes:

• Trying to assign 2D arrays directly
• Copying only row pointers instead of elements
• Not initializing distance matrix before algorithm

3. What will be the output distance matrix after running Floyd Warshall on the following graph with 3 vertices and adjacency matrix:

int graph[3][3] = {
  {0, 5, 999},
  {50, 0, 15},
  {30, 999, 0}
};

Assuming 999 represents no direct edge.

medium

A. [[0, 5, 20], [50, 0, 15], [30, 35, 0]]

B. [[0, 5, 999], [50, 0, 15], [30, 999, 0]]

C. [[0, 5, 999], [50, 0, 15], [30, 45, 0]]

D. [[0, 5, 20], [45, 0, 15], [30, 35, 0]]

Solution

1. Step 1: Initialize distance matrix

   Start with dist = graph:
   dist = [[0,5,999],[50,0,15],[30,999,0]]

2. Step 2: Update distances using Floyd Warshall

   Check if going through vertex 0 improves paths:
   dist[1][2] = min(15, dist[1][0]+dist[0][2]) = min(15, 50+999)=15 (no change)
   dist[2][1] = min(999, dist[2][0]+dist[0][1]) = min(999, 30+5)=35 (updated)
   Check through vertex 1:
   dist[0][2] = min(999, dist[0][1]+dist[1][2]) = min(999, 5+15)=20 (updated)
   dist[2][2] = min(0, dist[2][1]+dist[1][2]) = min(0, 35+15)=0 (no change)
   Check through vertex 2:
   dist[1][0] = min(50, dist[1][2]+dist[2][0]) = min(50, 15+30)=45 (updated)

3. Final Answer:

   [[0, 5, 20], [45, 0, 15], [30, 35, 0]] -> Option D

4. Quick Check:

   Updated shortest paths matrix = [[0, 5, 20], [45, 0, 15], [30, 35, 0]] [OK]

Hint: Check all intermediate vertices to update shortest paths [OK]

Common Mistakes:

• Not updating paths through intermediate vertices
• Confusing no edge (999) with zero
• Missing updates for reverse paths

4. Identify the error in this Floyd Warshall code snippet and select the fix:

for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j])
        dist[i][j] = dist[i][k] + dist[k][j];
    }
  }
}

medium

A. Check if dist[i][k] and dist[k][j] are not infinity before adding

B. No error; code is correct

C. Change loop order to i, j, k

D. Use max instead of min in the if condition

Solution

1. Step 1: Understand potential overflow in addition

   If dist[i][k] or dist[k][j] is infinity (representing no path), adding them causes incorrect results or overflow.

2. Step 2: Fix by checking for infinity before addition

   Before adding dist[i][k] + dist[k][j], ensure both are not infinity to avoid invalid updates.

3. Final Answer:

   Check if dist[i][k] and dist[k][j] are not infinity before adding -> Option A

4. Quick Check:

   Prevent invalid addition by checking infinity [OK]

Hint: Always check for infinity before adding distances [OK]

Common Mistakes:

• Ignoring infinity checks causing wrong updates
• Changing loop order incorrectly
• Using max instead of min for shortest path

5. Given a weighted directed graph with 4 vertices and adjacency matrix:

int graph[4][4] = {
  {0, 3, 999, 7},
  {8, 0, 2, 999},
  {5, 999, 0, 1},
  {2, 999, 999, 0}
};

Use Floyd Warshall to find the shortest path distance from vertex 0 to vertex 3 after all updates. What is the shortest distance?

hard

A. 8

B. 7

C. 6

D. 9

Solution

1. Step 1: Initialize distance matrix

   Start with dist = graph:
   dist = [[0,3,999,7],[8,0,2,999],[5,999,0,1],[2,999,999,0]]

2. Step 2: Update distances through intermediate vertices

   Check paths through vertex 0:
   dist[1][3] = min(999, dist[1][0]+dist[0][3]) = min(999, 8+7)=15
   dist[2][1] = min(999, dist[2][0]+dist[0][1]) = min(999, 5+3)=8
   dist[3][1] = min(999, dist[3][0]+dist[0][1]) = min(999, 2+3)=5
   Check paths through vertex 1:
   dist[0][2] = min(999, dist[0][1]+dist[1][2]) = min(999, 3+2)=5
   dist[0][3] = min(7, dist[0][1]+dist[1][3]) = min(7, 3+15)=7
   dist[3][2] = min(999, dist[3][1]+dist[1][2]) = min(999, 5+2)=7
   Check paths through vertex 2:
   dist[1][3] = min(15, dist[1][2]+dist[2][3]) = min(15, 2+1)=3 (updated)
   dist[0][3] = min(7, dist[0][2]+dist[2][3]) = min(7, 5+1)=6 (updated)
   Check paths through vertex 3:
   dist[2][0] = min(5, dist[2][3]+dist[3][0]) = min(5, 1+2)=3 (updated)

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Shortest path 0 to 3 = 6 [OK]

Hint: Update distances through all vertices stepwise [OK]

Common Mistakes:

• Not updating paths through all intermediate vertices
• Missing shorter path updates
• Confusing direct edge with shortest path