Floyd Warshall All Pairs Shortest Path in DSA Go - 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 shortest paths by considering each node as an intermediate step, checking if going through it shortens any path.

Execution Sample

DSA Go

for k := 0; k < V; k++ {
  for i := 0; i < V; i++ {
    for j := 0; j < V; j++ {
      if dist[i][k] + dist[k][j] < dist[i][j] {
        dist[i][j] = dist[i][k] + dist[k][j]
      }
    }
  }
}

This code updates the distance matrix by checking if going through node k shortens the path from i to j.

Execution Table

Step	Operation	Nodes (i,j,k)	Condition (dist[i][k]+dist[k][j]<dist[i][j])	Update	Distance Matrix State
1	Initialize dist matrix	-	-	Set dist[i][j] to direct edge or ∞	[[0, 3, ∞, 7], [8, 0, 2, ∞], [5, ∞, 0, 1], [2, ∞, ∞, 0]]
2	k=0, i=1, j=3	i=1, j=3, k=0	dist[1][0]+dist[0][3] = 8+7=15 < ∞	Update dist[1][3] = 15	[[0, 3, ∞, 7], [8, 0, 2, 15], [5, ∞, 0, 1], [2, ∞, ∞, 0]]
3	k=0, i=2, j=1	i=2, j=1, k=0	dist[2][0]+dist[0][1] = 5+3=8 < ∞	Update dist[2][1] = 8	[[0, 3, ∞, 7], [8, 0, 2, 15], [5, 8, 0, 1], [2, ∞, ∞, 0]]
4	k=1, i=0, j=2	i=0, j=2, k=1	dist[0][1]+dist[1][2] = 3+2=5 < ∞	Update dist[0][2] = 5	[[0, 3, 5, 7], [8, 0, 2, 15], [5, 8, 0, 1], [2, ∞, ∞, 0]]
5	k=2, i=1, j=3	i=1, j=3, k=2	dist[1][2]+dist[2][3] = 2+1=3 < 15	Update dist[1][3] = 3	[[0, 3, 5, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, ∞, ∞, 0]]
6	k=3, i=3, j=2	i=3, j=2, k=3	dist[3][3]+dist[3][2] = 0+∞=∞ < ∞? No	No update	[[0, 3, 5, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, ∞, ∞, 0]]
7	End	-	-	All pairs shortest paths computed	[[0, 3, 5, 7], [8, 0, 2, 3], [5, 8, 0, 1], [2, 5, 7, 0]]

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	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,∞,∞,0]]	[[0,3,∞,7],[8,0,2,15],[5,8,0,1],[2,∞,∞,0]]	[[0,3,5,7],[8,0,2,15],[5,8,0,1],[2,∞,∞,0]]	[[0,3,5,7],[8,0,2,3],[5,8,0,1],[2,∞,∞,0]]	[[0,3,5,7],[8,0,2,3],[5,8,0,1],[2,∞,∞,0]]	[[0,3,5,7],[8,0,2,3],[5,8,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 steps 2, 4, and 5 where updates happen only when the condition is true.

Why does the algorithm consider all nodes as intermediate nodes (k)?

Because shortest paths might go through any node. The algorithm tries all nodes as intermediates to find the shortest possible path, as seen by the outer loop over k in the execution table.

What happens if there is no direct edge between two nodes initially?

We set the distance to infinity (∞) initially. The algorithm tries to find shorter paths through intermediates. For example, dist[0][2] was ∞ at start but updated to 5 at step 4.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the updated distance from node 0 to node 2?

A 5

B 3

C ∞

D 7

💡 Hint

Check the 'Distance Matrix State' column at step 4 in the execution_table.

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

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look for the update of dist[1][3] to 3 in the execution_table rows.

If the initial distance from node 3 to node 2 was 4 instead of ∞, how would the final distance from node 0 to node 2 change?

A It would become 4

B It would remain 5

C It would become 7

D It would become ∞

💡 Hint

Consider how the algorithm updates dist[0][2] through intermediate nodes and check variable_tracker for dist changes.

Concept Snapshot

Floyd Warshall Algorithm:
- Uses a distance matrix dist[V][V]
- For each node k as intermediate:
  For each pair (i,j), update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- Finds shortest paths between all pairs
- Handles positive weights and ∞ for no direct edge
- Runs in O(V^3) time

Full Transcript

The 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 set to infinity. Then, it picks each node as an intermediate point and checks if going through it shortens the path between every pair of nodes. If yes, it updates the distance. This process repeats for all nodes as intermediates. The final matrix shows the shortest distances between all pairs. Key points include only updating when a shorter path is found, considering all nodes as intermediates, and initializing no-edge distances as infinity.

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 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 subset of edges connecting all vertices with minimum total weight, cycle detection finds cycles, and DFS is a traversal method. These are different from Floyd Warshall's all pairs shortest path goal.

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 Floyd Warshall with minimum spanning tree algorithms
• Thinking it only finds shortest path from one source
• Assuming it detects cycles
• Mixing it with traversal algorithms like DFS

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in Go, given graph as adjacency matrix and V as number of vertices?

easy

A. dist = graph

B. for i := 0; i < V; i++ { dist[i] = graph[i] }

C. for i := 0; i < V; i++ { for j := 0; j < V; j++ { dist[i][j] = graph[i][j] } }

D. dist := make([]int, V*V)

Solution

1. Step 1: Understand matrix copying in Go

   In Go, to copy a 2D slice (matrix), you must copy each element individually. Assigning one slice to another copies the reference, not the data.

2. Step 2: Analyze options

   for i := 0; i < V; i++ { for j := 0; j < V; j++ { dist[i][j] = graph[i][j] } } copies each element explicitly, correctly initializing dist. for i := 0; i < V; i++ { dist[i] = graph[i] } copies slice references, not elements. dist = graph assigns reference, not copy. dist := make([]int, V*V) creates a 1D slice, not a 2D matrix.

3. Final Answer:

   for i := 0; i < V; i++ { for j := 0; j < V; j++ { dist[i][j] = graph[i][j] } } -> Option C

4. Quick Check:

   Copy element-wise for matrix copy [OK]

Hint: Copy 2D slices element-wise to avoid reference issues [OK]

Common Mistakes:

• Assigning slices directly causing shared references
• Using 1D slice instead of 2D for matrix
• Not initializing inner slices before assignment
• Assuming slice assignment copies data

3. What will be the output distance matrix after running Floyd Warshall on the following graph represented as adjacency matrix (9999 means no direct edge):

graph := [][]int{
  {0, 3, 9999, 7},
  {8, 0, 2, 9999},
  {5, 9999, 0, 1},
  {2, 9999, 9999, 0},
}

medium

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

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

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

D. [[0, 3, 4, 6], [7, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]]

Solution

1. Step 1: Initialize distance matrix

   Start with given graph matrix where 9999 means no direct edge. Distances on diagonal are 0.

2. Step 2: Apply Floyd Warshall updates

   Check all triples (i, j, k) and update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After iterations, shortest paths are:
   dist[0][2] = min(9999, 3+2) = 5
   dist[0][3] = min(7, 3+2+1) = 6
   dist[1][0] = min(8, 2+1+2) = 7
   dist[1][3] = min(9999, 2+1) = 3
   dist[2][0] = min(5, 1+2) = 3
   dist[2][1] = min(9999, 1+2+3) = 6
   dist[3][1] = min(9999, 2+3) = 5
   dist[3][2] = min(9999, 2+3+2) = 7

3. Final Answer:

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

4. Quick Check:

   Floyd Warshall updates shortest paths correctly [OK]

Hint: Update dist[i][j] using intermediate k for all triples [OK]

Common Mistakes:

• Not updating paths through intermediate vertices
• Confusing no edge (9999) with zero
• Forgetting to update all pairs in nested loops
• Incorrectly summing distances

4. Consider this Go code snippet for Floyd Warshall. What is the bug causing incorrect shortest path results?

for k := 0; k < V; k++ {
  for i := 0; i < V; i++ {
    for j := 0; j < V; j++ {
      if dist[i][k] + dist[k][j] < dist[i][j] {
        dist[i][j] = dist[i][k] + dist[k][j]
      }
    }
  }
}

medium

A. Missing check for dist[i][k] or dist[k][j] being infinity before addition

B. No bug; code is correct

C. Loop order should be i, j, k instead of k, i, j

D. Should use <= instead of < in if condition

Solution

1. Step 1: Understand the addition of distances

   When dist[i][k] or dist[k][j] is infinity (e.g., 9999), adding them can cause integer overflow or incorrect comparisons.

2. Step 2: Identify missing checks

   The code does not check if dist[i][k] or dist[k][j] is infinity before adding. This can cause wrong updates to dist[i][j]. Proper code should skip addition if either is infinity.

3. Final Answer:

   Missing check for dist[i][k] or dist[k][j] being infinity before addition -> Option A

4. Quick Check:

   Check infinity before adding distances [OK]

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

Common Mistakes:

• Ignoring infinity checks causing wrong updates
• Changing loop order unnecessarily
• Using <= instead of < does not fix logic
• Assuming code is correct without boundary checks

5. Given a graph with vertices representing cities and edges representing travel times, how can Floyd Warshall be adapted to also reconstruct the shortest path between any two cities?

hard

A. Store all paths explicitly in a list during the algorithm

B. Maintain a separate predecessor matrix updated during relaxation to track paths

C. Run Dijkstra's algorithm for each city instead

D. Use BFS instead of Floyd Warshall for path reconstruction

Solution

1. Step 1: Understand Floyd Warshall's limitation

   Floyd Warshall computes shortest distances but does not store path details by default.

2. Step 2: Use predecessor matrix for path reconstruction

   By maintaining a predecessor matrix where predecessor[i][j] stores the vertex before j on the shortest path from i, we can reconstruct the path after the algorithm finishes.

3. Step 3: Other options analysis

   Storing all paths explicitly is inefficient. Running Dijkstra repeatedly is possible but less efficient for dense graphs. BFS is not suitable for weighted graphs.

4. Final Answer:

   Maintain a separate predecessor matrix updated during relaxation to track paths -> Option B

5. Quick Check:

   Predecessor matrix enables path reconstruction [OK]

Hint: Use predecessor matrix to rebuild shortest paths [OK]

Common Mistakes:

• Not tracking predecessors, so no path info
• Trying to store all paths explicitly causing inefficiency
• Confusing BFS with weighted shortest path algorithms
• Using Dijkstra repeatedly instead of Floyd Warshall