Floyd Warshall All Pairs Shortest Path in DSA Rust - 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 distance[i

↓

Repeat for all k, i, j

↓

Final shortest paths matrix

The algorithm updates shortest paths by considering each node as an intermediate step, checking if going through it shortens the path between every pair of nodes.

Execution Sample

DSA Rust

let mut dist = vec![
  vec![0, 3, 1000],
  vec![2, 0, 5],
  vec![1000, 1, 0],
];
// 1000 means no direct edge

This code initializes a distance matrix for 3 nodes, where 1000 represents no direct edge between nodes.

Execution Table

Step	Operation	Intermediate k	Pair (i,j)	Old dist[i][j]	New dist[i][j]	Updated?	Distance Matrix State
1	Initialize	-	-	-	-	No	[[0,3,1000],[2,0,5],[1000,1,0]]
2	Check path via k=0	0	(0,0)	0	0	No	[[0,3,1000],[2,0,5],[1000,1,0]]
3	Check path via k=0	0	(0,1)	3	3	No	[[0,3,1000],[2,0,5],[1000,1,0]]
4	Check path via k=0	0	(0,2)	1000	1000	No	[[0,3,1000],[2,0,5],[1000,1,0]]
5	Check path via k=0	0	(1,0)	2	2	No	[[0,3,1000],[2,0,5],[1000,1,0]]
6	Check path via k=0	0	(1,1)	0	0	No	[[0,3,1000],[2,0,5],[1000,1,0]]
7	Check path via k=0	0	(1,2)	5	5	No	[[0,3,1000],[2,0,5],[1000,1,0]]
8	Check path via k=0	0	(2,0)	1000	1000	No	[[0,3,1000],[2,0,5],[1000,1,0]]
9	Check path via k=0	0	(2,1)	1	1	No	[[0,3,1000],[2,0,5],[1000,1,0]]
10	Check path via k=0	0	(2,2)	0	0	No	[[0,3,1000],[2,0,5],[1000,1,0]]
11	Check path via k=1	1	(0,0)	0	0	No	[[0,3,1000],[2,0,5],[1000,1,0]]
12	Check path via k=1	1	(0,1)	3	3	No	[[0,3,1000],[2,0,5],[1000,1,0]]
13	Check path via k=1	1	(0,2)	1000	8	Yes	[[0,3,8],[2,0,5],[1000,1,0]]
14	Check path via k=1	1	(1,0)	2	2	No	[[0,3,8],[2,0,5],[1000,1,0]]
15	Check path via k=1	1	(1,1)	0	0	No	[[0,3,8],[2,0,5],[1000,1,0]]
16	Check path via k=1	1	(1,2)	5	5	No	[[0,3,8],[2,0,5],[1000,1,0]]
17	Check path via k=1	1	(2,0)	1000	3	Yes	[[0,3,8],[2,0,5],[3,1,0]]
18	Check path via k=1	1	(2,1)	1	1	No	[[0,3,8],[2,0,5],[3,1,0]]
19	Check path via k=1	1	(2,2)	0	0	No	[[0,3,8],[2,0,5],[3,1,0]]
20	Check path via k=2	2	(0,0)	0	0	No	[[0,3,8],[2,0,5],[3,1,0]]
21	Check path via k=2	2	(0,1)	3	3	No	[[0,3,8],[2,0,5],[3,1,0]]
22	Check path via k=2	2	(0,2)	8	8	No	[[0,3,8],[2,0,5],[3,1,0]]
23	Check path via k=2	2	(1,0)	2	2	No	[[0,3,8],[2,0,5],[3,1,0]]
24	Check path via k=2	2	(1,1)	0	0	No	[[0,3,8],[2,0,5],[3,1,0]]
25	Check path via k=2	2	(1,2)	5	5	No	[[0,3,8],[2,0,5],[3,1,0]]
26	Check path via k=2	2	(2,0)	3	3	No	[[0,3,8],[2,0,5],[3,1,0]]
27	Check path via k=2	2	(2,1)	1	1	No	[[0,3,8],[2,0,5],[3,1,0]]
28	Check path via k=2	2	(2,2)	0	0	No	[[0,3,8],[2,0,5],[3,1,0]]

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

Variable Tracker

Variable	Start	After k=0	After k=1	After k=2 (Final)
dist	[[0,3,1000],[2,0,5],[1000,1,0]]	[[0,3,1000],[2,0,5],[1000,1,0]]	[[0,3,8],[2,0,5],[3,1,0]]	[[0,3,8],[2,0,5],[3,1,0]]

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 the shortest path by checking if going through node k gives a shorter route than the current known distance. See rows 13 and 17 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 could be part of the shortest path between any two nodes i and j. The algorithm ensures all possible intermediate nodes are checked, as shown in steps 2 to 28.

What does the large number (1000) represent in the distance matrix?

It represents no direct edge between nodes, meaning initially the path is considered very long or infinite. Updates happen only if a shorter path is found, as seen in step 13 where 1000 changes to 8.

Visual Quiz - 3 Questions

Look at the execution table at step 7. What is the new distance from node 1 to node 2?

A 5

B 8

C 1000

D 3

💡 Hint

Check the 'New dist[i][j]' column at step 7 in the execution_table.

At which step does the distance from node 2 to node 0 first get updated?

A Step 9

B Step 13

C Step 17

D Step 22

💡 Hint

Look for the first step where 'Updated?' is Yes and pair (2,0) is checked.

If the initial distance from node 0 to node 2 was 7 instead of 1000, how would the final distance change?

A Final distance would remain 11

B Final distance would be 7

C Final distance would be 8

D Final distance would be 3

💡 Hint

Consider how initial distances affect updates in the variable_tracker and execution_table.

Concept Snapshot

Floyd Warshall Algorithm:
- Uses a distance matrix for all node pairs
- Iterates over each node as intermediate (k)
- Updates dist[i][j] if dist[i][k] + dist[k][j] < dist[i][j]
- Handles negative edges but no negative cycles
- Final matrix shows shortest paths 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 with a large number (like 1000). The algorithm 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 intermediate until no shorter paths are found. The final matrix shows the shortest distances between all pairs. The execution table shows each step, the pair checked, old and new distances, and whether an update happened. The variable tracker shows how the distance matrix changes after considering each intermediate node. Key moments clarify why updates happen only when shorter paths are found, why all pairs are checked for each intermediate node, and what the large number means. The visual quiz tests understanding of specific steps and effects of initial distances.

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 directed graph

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

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 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 for all vertex pairs [OK]

Common Mistakes:

• Confusing with minimum spanning tree algorithms
• Thinking it only finds shortest path from one source
• Mixing with cycle detection or traversal algorithms

2. Which of the following Rust code snippets correctly initializes the distance matrix for Floyd Warshall with 3 vertices and no edges (infinity represented by i32::MAX)?

easy

A. let mut dist = vec![vec![0; 3]; 3]; for i in 0..3 { dist[i][i] = i32::MAX; }

B. let mut dist = vec![vec![i32::MAX; 3]; 3]; for i in 0..3 { dist[i][i] = 0; }

C. let mut dist = vec![vec![i32::MAX; 3]; 3]; for i in 0..3 { dist[i][i] = i32::MAX; }

D. let mut dist = vec![vec![0; 3]; 3]; for i in 0..3 { dist[i][i] = 0; }

Solution

1. Step 1: Initialize matrix with infinity

   We start with all distances as infinity (i32::MAX) because no edges exist initially.

2. Step 2: Set distance from vertex to itself as zero

   Distance from a vertex to itself is zero, so dist[i][i] = 0 for all i.

3. Final Answer:

   let mut dist = vec![vec![i32::MAX; 3]; 3]; for i in 0..3 { dist[i][i] = 0; } -> Option B

4. Quick Check:

   Init with i32::MAX, diagonal zero [OK]

Hint: Set diagonal to zero, others to infinity for dist matrix [OK]

Common Mistakes:

• Setting diagonal to infinity instead of zero
• Initializing with zeros everywhere
• Mixing up i32::MAX and 0 values

3. Given the following Rust code snippet implementing Floyd Warshall on a graph with 3 vertices and edges: 0->1 (4), 1->2 (3), 0->2 (10), what is the shortest distance from vertex 0 to vertex 2 after running the algorithm?

let n = 3;
let mut dist = vec![vec![i32::MAX; n]; n];
for i in 0..n { dist[i][i] = 0; }
dist[0][1] = 4;
dist[1][2] = 3;
dist[0][2] = 10;

for k in 0..n {
    for i in 0..n {
        for j in 0..n {
            if dist[i][k] != i32::MAX && dist[k][j] != i32::MAX {
                dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j]);
            }
        }
    }
}

println!("{}", dist[0][2]);

medium

A. 7

B. 10

C. 4

D. 3

Solution

1. Step 1: Initial distances

   dist[0][2] starts at 10, dist[0][1] = 4, dist[1][2] = 3.

2. Step 2: Update via intermediate vertex 1

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

3. Final Answer:

   7 -> Option A

4. Quick Check:

   0->1->2 = 7 < 10 [OK]

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

Common Mistakes:

• Not updating dist[0][2] via vertex 1
• Confusing initial edge weights with final shortest paths
• Ignoring i32::MAX checks causing overflow

4. Identify the bug in this Rust Floyd Warshall implementation snippet that causes incorrect shortest path results:

for k in 0..n {
    for i in 0..n {
        for j in 0..n {
            if dist[i][k] + dist[k][j] < dist[i][j] {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

medium

A. Using '<' instead of '<=' in comparison

B. Incorrect loop order; should be i, j, k

C. Missing check for i32::MAX before addition causing overflow

D. Not initializing diagonal elements to zero

Solution

1. Step 1: Analyze addition of distances

   Adding dist[i][k] + dist[k][j] without checking if either is i32::MAX can cause integer overflow.

2. Step 2: Importance of checks before addition

   Proper Floyd Warshall requires checking dist[i][k] != i32::MAX and dist[k][j] != i32::MAX before adding to avoid overflow and incorrect updates.

3. Final Answer:

   Missing check for i32::MAX 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 adding i32::MAX
• Changing loop order unnecessarily
• Confusing comparison operators
• Forgetting to initialize diagonal distances

5. You have a graph with 4 vertices and edges: 0->1 (5), 1->2 (2), 2->3 (1), and 0->3 (20). Using Floyd Warshall, what is the shortest distance from vertex 0 to vertex 3 after the algorithm completes?

hard

A. 8

B. 20

C. 5

D. 10

Solution

1. Step 1: Initial distances

   Direct edge 0->3 is 20. Other edges: 0->1=5, 1->2=2, 2->3=1.

2. Step 2: Calculate path 0->1->2->3

   Sum is 5 + 2 + 1 = 8, which is less than 20, so shortest path updates to 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   0->1->2->3 = 8 < 20 [OK]

Hint: Sum edges along path to find shorter distance than direct edge [OK]

Common Mistakes:

• Choosing direct edge weight without checking intermediate paths
• Adding edges incorrectly
• Ignoring path through multiple vertices