Floyd Warshall All Pairs Shortest Path in DSA Java - 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

Yes No↓

Update dist[i

↓

Repeat for all k

↓

Final shortest paths matrix

The algorithm updates the 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 Java

int[][] dist = {
  {0, 3, 999, 7},
  {8, 0, 2, 999},
  {5, 999, 0, 1},
  {2, 999, 999, 0}
};
// Floyd Warshall updates dist

This code initializes a distance matrix with 4 nodes and runs Floyd Warshall 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,999,7],[8,0,2,999],[5,999,0,1],[2,999,999,0]]
2	Check path via k=0	0	(0,2)	999	999	No	[[0,3,999,7],[8,0,2,999],[5,999,0,1],[2,999,999,0]]
3	Check path via k=0	0	(1,3)	999	15	Yes	[[0,3,999,7],[8,0,2,15],[5,999,0,1],[2,999,999,0]]
4	Check path via k=0	0	(2,1)	999	8	Yes	[[0,3,999,7],[8,0,2,15],[5,8,0,1],[2,999,999,0]]
5	Check path via k=0	0	(3,1)	999	5	Yes	[[0,3,999,7],[8,0,2,15],[5,8,0,1],[2,5,999,0]]
6	Check path via k=1	1	(0,2)	999	5	Yes	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,999,0]]
7	Check path via k=1	1	(3,2)	999	7	Yes	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
8	Check path via k=2	2	(0,3)	7	6	Yes	[[0,3,5,6],[8,0,2,15],[5,8,0,1],[2,5,7,0]]
9	Check path via k=2	2	(1,3)	15	3	Yes	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
10	Check path via k=3	3	(1,2)	2	2	No	[[0,3,5,6],[8,0,2,3],[5,8,0,1],[2,5,7,0]]
11	Check path via k=3	3	(2,1)	8	6	Yes	[[0,3,5,6],[8,0,2,3],[5,6,0,1],[2,5,7,0]]
12	Check path via k=3	3	(3,2)	7	7	No	[[0,3,5,6],[8,0,2,3],[5,6,0,1],[2,5,7,0]]
13	Finish	-	-	-	-	No	[[0,3,5,6],[8,0,2,3],[5,6,0,1],[2,5,7,0]]

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

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
dist	[[0,3,999,7],[8,0,2,999],[5,999,0,1],[2,999,999,0]]	[[0,3,999,7],[8,0,2,15],[5,999,0,1],[2,999,999,0]]	[[0,3,999,7],[8,0,2,15],[5,8,0,1],[2,5,999,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],[8,0,2,3],[5,6,0,1],[2,5,7,0]]	[[0,3,5,6],[8,0,2,3],[5,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 the intermediate node k gives a shorter path. This is shown in execution_table rows 3 and 6 where updates happen only when the new path is shorter.

Why do we need to consider all nodes as intermediate nodes k?

Because shortest paths might go through multiple nodes. The algorithm ensures all possible intermediate nodes are checked, as seen in the execution_table steps where k changes from 0 to 3.

Why does the distance matrix start with 999 for no direct path?

999 represents infinity or no direct connection. It allows the algorithm to find shorter paths through intermediate nodes, as seen in step 6 where dist[0][2] updates from 999 to 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the new distance from node 0 to node 2?

A 999

B 5

C 3

D 2

💡 Hint

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

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

A Step 9

B Step 3

C Step 11

D Step 6

💡 Hint

Look for the pair (1,3) and the updated distance 3 in execution_table.

If the initial distance from node 3 to node 1 was 4 instead of 999, how would the distance matrix change after step 5?

A dist[3][1] would update to 3

B dist[3][1] would update to 5

C dist[3][1] would remain 4, no update

D dist[3][1] would update to 2

💡 Hint

Check variable_tracker for dist[3][1] after step 5 and consider if 4 is less than the updated value 5.

Concept Snapshot

Floyd Warshall Algorithm:
- Uses dynamic programming to find shortest paths between all pairs of nodes.
- Iterates over all nodes as intermediate points (k).
- Updates dist[i][j] if dist[i][k] + dist[k][j] < dist[i][j].
- Handles negative edges but no negative cycles.
- Time complexity: O(n^3) for n nodes.

Full Transcript

Floyd Warshall algorithm starts with a distance matrix representing direct distances between nodes, using a large number like 999 for no direct path. It then picks each node as an intermediate node k and checks for every pair of nodes (i, j) if going through k shortens the path. If yes, it updates the distance. This process repeats for all k, resulting in the shortest distances between all pairs. The execution table shows step-by-step updates, and the variable tracker records the distance matrix changes. Key points include why updates happen only when shorter paths are found, the need to consider all nodes as intermediates, and the use of 999 to represent no direct path.

Practice

1. What does the Floyd Warshall algorithm primarily compute in a graph?

easy

A. Shortest paths between all pairs of vertices

B. Minimum spanning tree of the graph

C. Depth-first traversal order

D. Maximum flow between two nodes

Solution

1. Step 1: Understand Floyd Warshall purpose

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

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree, depth-first traversal, and maximum flow solve different problems, not all pairs shortest paths.

3. Final Answer:

   Shortest paths between all pairs of vertices -> Option A

4. Quick Check:

   Floyd Warshall = All pairs shortest paths [OK]

Hint: Floyd Warshall = shortest paths for all vertex pairs [OK]

Common Mistakes:

• Confusing with Dijkstra's single-source shortest path
• Thinking it finds minimum spanning tree
• Mixing with traversal algorithms

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

easy

A. for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = (i == j) ? 0 : Integer.MAX_VALUE;

B. for (int i = 0; i < V; i++) dist[i] = new int[V];

C. dist = new int[V][V]; for (int i = 0; i < V; i++) dist[i][i] = 1;

D. for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = 0;

Solution

1. Step 1: Understand initialization needs

   Distance from a vertex to itself should be 0, and to others should be infinity (represented by Integer.MAX_VALUE).

2. Step 2: Check each option

   for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = (i == j) ? 0 : Integer.MAX_VALUE; correctly sets 0 for same vertices and max value for others. for (int i = 0; i < V; i++) dist[i] = new int[V]; only initializes array but not values. dist = new int[V][V]; for (int i = 0; i < V; i++) dist[i][i] = 1; sets diagonal to 1 incorrectly. for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = 0; sets all to 0, which is wrong.

3. Final Answer:

   for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = (i == j) ? 0 : Integer.MAX_VALUE; -> Option A

4. Quick Check:

   Initialize dist[i][i] = 0, others = infinity [OK]

Hint: Set zero for same nodes, max value for others [OK]

Common Mistakes:

• Not setting distance to self as zero
• Setting all distances to zero
• Forgetting to initialize the matrix fully

3. What will be the output distance matrix after running Floyd Warshall on this graph with 3 vertices and edges: 0->1=4, 1->2=3, 0->2=10?

int V = 3;
int[][] dist = {
  {0, 4, 10},
  {Integer.MAX_VALUE, 0, 3},
  {Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
};
// Floyd Warshall algorithm applied here

medium

A. [[0, 4, 3], [∞, 0, 3], [∞, ∞, 0]]

B. [[0, 4, 10], [∞, 0, 3], [∞, ∞, 0]]

C. [[0, 7, 10], [∞, 0, 3], [∞, ∞, 0]]

D. [[0, 4, 7], [∞, 0, 3], [∞, ∞, 0]]

Solution

1. Step 1: Initial distances

   Start with dist matrix: 0->1=4, 1->2=3, 0->2=10, others infinity or 0 on diagonal.

2. Step 2: Update using intermediate vertices

   Check if path 0->1->2 is shorter than 0->2 directly: 4 + 3 = 7 < 10, so update dist[0][2] = 7.

3. Final Answer:

   [[0, 4, 7], [∞, 0, 3], [∞, ∞, 0]] -> Option D

4. Quick Check:

   0->2 updated to 7 via 1 [OK]

Hint: Check if indirect path is shorter than direct [OK]

Common Mistakes:

• Not updating indirect shorter paths
• Confusing infinity with zero
• Ignoring intermediate vertex updates

4. Identify the bug in this Floyd Warshall code snippet:

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] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

Assume dist uses Integer.MAX_VALUE for infinity.

medium

A. Missing initialization of dist matrix

B. Loop variables are in wrong order

C. No check for Integer.MAX_VALUE before addition causing overflow

D. Should use '>' instead of '<' in if condition

Solution

1. Step 1: Understand addition with infinity

   Adding Integer.MAX_VALUE + any positive number causes overflow and incorrect results.

2. Step 2: Check code for safety

   Code lacks checks to ensure dist[i][k] and dist[k][j] are not Integer.MAX_VALUE before adding.

3. Final Answer:

   No check for Integer.MAX_VALUE before addition causing overflow -> Option C

4. Quick Check:

   Check for infinity before addition to avoid overflow [OK]

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

Common Mistakes:

• Ignoring overflow from Integer.MAX_VALUE + number
• Assuming loops order causes error
• Confusing comparison operator direction

5. Given a graph with 4 vertices and edges:
0->1=5, 0->3=10, 1->2=3, 2->3=1
Use Floyd Warshall to find the shortest distance from vertex 0 to 3 after all updates.
What is the shortest distance from 0 to 3?

hard

A. 10

B. 9

C. 8

D. 7

Solution

1. Step 1: Initial distances

   Direct edges: 0->1=5, 0->3=10, 1->2=3, 2->3=1. Other distances are infinity or 0 on diagonal.

2. Step 2: Check indirect paths

   Path 0->1->2->3 distance = 5 + 3 + 1 = 9, which is less than direct 0->3=10, so update shortest distance to 9.

3. Final Answer:

   9 -> Option B

4. Quick Check:

   0->1->2->3 = 9 < 10 [OK]

Hint: Sum edges along path to find shortest distance [OK]

Common Mistakes:

• Ignoring multi-step paths
• Choosing direct edge without checking alternatives
• Adding edges incorrectly