Floyd Warshall All Pairs Shortest Path in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What problem does the Floyd Warshall algorithm solve?

It finds the shortest paths between all pairs of nodes in a weighted graph, including graphs with negative edge weights but no negative cycles.

intermediate

What is the main idea behind the Floyd Warshall algorithm?

It uses dynamic programming to update shortest paths by considering each node as an intermediate point, improving paths step-by-step.

beginner

In Floyd Warshall, what does the matrix entry dist[i][j] represent?

The shortest distance from node i to node j considering intermediate nodes processed so far.

beginner

What is the time complexity of the Floyd Warshall algorithm?

O(n³), where n is the number of nodes in the graph.

intermediate

Can Floyd Warshall detect negative weight cycles? If yes, how?

Yes, by checking if any dist[i][i] becomes negative after the algorithm finishes, indicating a negative cycle reachable from node i.

What does Floyd Warshall algorithm use to find shortest paths?

A Divide and conquer

B Greedy approach

C Backtracking

D Dynamic programming

Floyd Warshall uses dynamic programming to iteratively improve shortest paths.

What is the initial value of dist[i][j] if there is no direct edge between i and j?

A 0

B 1

C Infinity (a very large number)

D -1

Distances between nodes without direct edges are set to infinity to represent no known path initially.

Which of these graphs can Floyd Warshall handle correctly?

A Graphs with negative weight edges but no negative cycles

B Graphs with negative weight cycles

C Only unweighted graphs

D Only directed acyclic graphs

Floyd Warshall works with negative edges but fails if negative cycles exist.

What does a negative value in dist[i][i] after running Floyd Warshall indicate?

A Shortest path found

B Negative weight cycle reachable from node i

C No path exists

D Graph is disconnected

A negative dist[i][i] means a negative cycle exists involving node i.

What is the space complexity of Floyd Warshall algorithm for a graph with n nodes?

A O(n²)

B O(n)

C O(n³)

D O(1)

The algorithm stores a distance matrix of size n by n, so space complexity is O(n²).

Explain how Floyd Warshall algorithm updates the shortest path matrix step-by-step.

Think about how adding one intermediate node at a time can improve paths.

Describe how Floyd Warshall can detect negative weight cycles in a graph.

Focus on what the diagonal of the distance matrix represents after the algorithm finishes.

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