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 stop, improving distances step-by-step.

Execution Sample

DSA C#

int INF = int.MaxValue / 2; // To avoid overflow
int[,] dist = {
  {0, 3, INF, 7},
  {8, 0, 2, INF},
  {5, INF, 0, 1},
  {2, INF, INF, 0}
};
FloydWarshall(dist);

This code runs Floyd Warshall on a 4-node graph with initial distances, updating to shortest paths.

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 path via k=0	0	(1,2)	2	2	No	[[0,3,∞,7],[8,0,2,∞],[5,∞,0,1],[2,∞,∞,0]]
3	Check path via k=0	0	(1,3)	∞	10	Yes	[[0,3,∞,7],[8,0,2,10],[5,∞,0,1],[2,∞,∞,0]]
4	Check path via k=0	0	(2,1)	∞	8	Yes	[[0,3,∞,7],[8,0,2,10],[5,8,0,1],[2,∞,∞,0]]
5	Check path via k=0	0	(3,1)	∞	2	Yes	[[0,3,∞,7],[8,0,2,10],[5,8,0,1],[2,∞,∞,0]]
6	Check path via k=1	1	(0,2)	∞	5	Yes	[[0,3,5,7],[8,0,2,10],[5,8,0,1],[2,∞,∞,0]]
7	Check path via k=1	1	(3,2)	∞	12	Yes	[[0,3,5,7],[8,0,2,10],[5,8,0,1],[2,∞,12,0]]
8	Check path via k=2	2	(0,1)	3	4	Yes	[[0,4,5,7],[8,0,2,10],[5,8,0,1],[2,∞,12,0]]
9	Check path via k=2	2	(1,3)	10	3	Yes	[[0,4,5,7],[8,0,2,3],[5,8,0,1],[2,∞,12,0]]
10	Check path via k=3	3	(1,0)	8	5	Yes	[[0,4,5,7],[5,0,2,3],[5,8,0,1],[2,∞,12,0]]
11	Check path via k=3	3	(3,1)	2	6	Yes	[[0,4,5,7],[5,0,2,3],[5,8,0,1],[2,6,12,0]]
12	Check path via k=3	3	(3,2)	12	7	Yes	[[0,4,5,7],[5,0,2,3],[5,8,0,1],[2,6,7,0]]
13	End	-	-	-	-	No	[[0,4,5,7],[5,0,2,3],[5,8,0,1],[2,6,7,0]]

💡 All intermediate nodes k processed; shortest paths finalized.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	Final
dist[1][3]	∞	10	10	3	3	3
dist[0][2]	∞	∞	5	5	5	5
dist[3][2]	∞	∞	12	12	7	7
dist[3][1]	∞	∞	2	2	6	6
dist[1][0]	8	8	8	8	5	5

Key Moments - 3 Insights

Why do we update dist[i][j] only if dist[i][k] + dist[k][j] is smaller?

Because Floyd Warshall finds shorter paths by checking if going through k improves the distance. See steps 3 and 6 where updates happen only when the new path is shorter.

Why do we consider all pairs (i, j) for each intermediate node k?

Because any node k can be an intermediate stop between any i and j. The algorithm ensures all possible paths through k are checked, as shown in the repeated checks for each k in the execution table.

What does '∞' mean in the distance matrix and how is it handled?

'∞' means no direct path exists initially. The algorithm treats it as a very large number and updates it when a shorter path is found, as seen when dist[0][2] changes from ∞ to 5 at step 6.

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the new distance for pair (0,2)?

A ∞

B 5

C 3

D 7

💡 Hint

Check the 'New dist[i][j]' column for step 6 in the execution table.

At which step does the distance from node 1 to node 3 first get updated to 3?

A Step 9

B Step 12

C Step 3

D Step 6

💡 Hint

Look for dist[1][3] updates in the execution table rows.

If the initial distance dist[3][1] was 10 instead of ∞, how would the final distance change?

A Final dist[3][1] would be 2

B Final dist[3][1] would be 10

C Final dist[3][1] would remain 6

D Final dist[3][1] would be ∞

💡 Hint

Check variable_tracker for dist[3][1] and how updates happen through steps.

Concept Snapshot

Floyd Warshall Algorithm:
- Uses a distance matrix dist[][]
- For each node k as intermediate:
  update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- Handles all pairs (i,j) for shortest paths
- Time complexity: O(n^3)
- Works with positive or zero edge weights

Full Transcript

Floyd Warshall algorithm finds shortest paths between all pairs of nodes in a graph. It starts with a distance matrix representing direct edges or infinity if no direct edge exists. The algorithm iterates over each node as an intermediate point k. For every pair of nodes (i, j), it checks if going through k offers a shorter path than the current known distance. If yes, it updates the distance. This process repeats for all nodes k, gradually improving the shortest path estimates. The final matrix shows the shortest distances between every pair of nodes. Key points include understanding why updates happen only when a shorter path is found, why all pairs are checked for each intermediate node, and how infinity represents no direct path initially. The algorithm runs in cubic time and works for graphs with positive or zero edge weights.

Practice

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

easy

A. To perform a depth-first search traversal

B. To find the minimum spanning tree of a graph

C. To detect cycles in a graph

D. To find the shortest paths between all pairs of vertices in a weighted 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, including negative weights but no negative cycles.

2. Step 2: Compare with other algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total weight, cycle detection finds loops, and DFS is a traversal method, none of which match Floyd Warshall's purpose.

3. Final Answer:

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

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 only finds shortest path from one source
• Assuming it works with negative cycles

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in C# when given an adjacency matrix graph of size V?

easy

A. for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = graph[i, j]; } }

B. for (int i = 0; i < V; i++) { dist[i, i] = 0; } for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (i != j) dist[i, j] = int.MaxValue; } }

C. for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = 0; } }

D. for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = -1; } }"

Solution

1. Step 1: Understand initialization for Floyd Warshall

   The distance matrix dist should start as a copy of the adjacency matrix graph because it holds initial edge weights or infinity where no edge exists.

2. Step 2: Check each option

   for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = graph[i, j]; } } copies graph to dist, which is correct. for (int i = 0; i < V; i++) { dist[i, i] = 0; } for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (i != j) dist[i, j] = int.MaxValue; } } sets 0 for diagonal and max value elsewhere but does not copy actual edges. Options C and D incorrectly set all distances to 0 or -1.

3. Final Answer:

   for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i, j] = graph[i, j]; } } -> Option A

4. Quick Check:

   Initialize dist as graph copy [OK]

Hint: Copy graph matrix to dist for Floyd Warshall start [OK]

Common Mistakes:

• Setting all distances to zero
• Not copying actual edge weights
• Using -1 instead of infinity for no edge

3. Consider the following C# code snippet implementing Floyd Warshall on a graph with 3 vertices and adjacency matrix:

int V = 3;
int[,] graph = {
  {0, 5, int.MaxValue},
  {50, 0, 15},
  {30, int.MaxValue, 0}
};

int[,] dist = new int[V, V];
for (int i = 0; i < V; i++)
  for (int j = 0; j < V; j++)
    dist[i, j] = graph[i, j];

for (int k = 0; k < V; k++) {
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue && dist[i, k] + dist[k, j] < dist[i, j]) {
        dist[i, j] = dist[i, k] + dist[k, j];
      }
    }
  }
}

// Print dist matrix
for (int i = 0; i < V; i++) {
  for (int j = 0; j < V; j++) {
    Console.Write(dist[i, j] == int.MaxValue ? "INF " : dist[i, j] + " ");
  }
  Console.WriteLine();
}

What is the printed output?

medium

A. 0 5 20
50 0 15
30 INF 0

B. 0 5 20
45 0 15
30 35 0

C. 0 5 INF
50 0 15
30 INF 0

D. 0 5 15
50 0 15
30 35 0

Solution

1. Step 1: Initialize dist matrix

   dist starts as: 0 5 INF 50 0 15 30 INF 0

2. Step 2: Apply Floyd Warshall updates

   Check paths through each vertex k: - k=0: Update dist[1,2] via 1->0->2: 50 + INF no update; dist[2,1] via 2->0->1: 30 + 5 = 35 < INF, update dist[2,1] = 35 - k=1: Update dist[0,2] via 0->1->2: 5 + 15 = 20 < INF, update dist[0,2] = 20 - k=2: No further improvements Final dist: 0 5 20 45 0 15 30 35 0

3. Final Answer:

   0 5 20 45 0 15 30 35 0 -> Option B

4. Quick Check:

   Floyd Warshall updates shortest paths correctly [OK]

Hint: Check all intermediate vertices k for shorter paths [OK]

Common Mistakes:

• Not updating dist when shorter path found
• Confusing INF with int.MaxValue in output
• Missing updates for indirect paths

4. The following C# code attempts to implement Floyd Warshall but produces incorrect results. What is the main bug?

int V = 3;
int[,] dist = new int[V, V];
for (int i = 0; i < V; i++)
  for (int j = 0; j < V; j++)
    dist[i, j] = graph[i, j];

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

Choose the correct bug:

medium

A. The condition does not check for int.MaxValue before addition

B. The initialization of dist is missing

C. The order of loops is incorrect; k should be the outer loop

D. The code uses wrong indices in the if condition

Solution

1. Step 1: Analyze loop order

   Floyd Warshall requires the outer loop to be over intermediate vertex k, then loops over i and j to update paths through k.

2. Step 2: Identify impact of loop order

   Current code loops i, j, then k, which does not correctly consider all intermediate vertices before updating distances, leading to incorrect results.

3. Final Answer:

   The order of loops is incorrect; k should be the outer loop -> Option C

4. Quick Check:

   Loop order: k outermost for Floyd Warshall [OK]

Hint: Outer loop must be intermediate vertex k [OK]

Common Mistakes:

• Not checking for int.MaxValue before addition
• Incorrect loop nesting order
• Forgetting to initialize dist properly

5. You have a weighted directed graph with 4 vertices and the following adjacency matrix (where INF means no direct edge):

int INF = int.MaxValue;
int[,] graph = {
  {0, 3, INF, 7},
  {8, 0, 2, INF},
  {5, INF, 0, 1},
  {2, INF, INF, 0}
};

Using Floyd Warshall, what is the shortest distance from vertex 3 to vertex 1 after the algorithm completes?

hard

A. 5

B. 7

C. 6

D. 3

Solution

1. Step 1: Understand the graph and indexing

   Vertices are 0-based: vertex 3 means index 3, vertex 1 means index 1. Initial dist[3,1] = INF (no direct edge).

2. Step 2: Apply Floyd Warshall updates to find shortest path from 3 to 1

   Check possible paths: - Direct: INF - Via 0: dist[3,0] + dist[0,1] = 2 + 3 = 5 - Via 2: dist[3,2] + dist[2,1] = INF + INF = INF - Other paths do not improve Therefore shortest distance is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Shortest path 3->0->1 = 2+3=5 [OK]

Hint: Trace paths through intermediate vertices to find shortest distance [OK]

Common Mistakes:

• Confusing vertex numbering (0-based vs 1-based)
• Ignoring indirect paths through intermediate vertices
• Assuming direct edge must exist