Floyd Warshall All Pairs Shortest Path in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd Warshall on a simple graph

What is the output distance matrix after running Floyd Warshall on this graph?

Graph edges with weights:
0 -> 1 (3), 0 -> 2 (8), 1 -> 2 (2), 2 -> 3 (1), 3 -> 0 (4)

Use 999 as infinity for no direct edge.
Initial distance matrix (4x4):
[[0, 3, 8, 999], [999, 0, 2, 999], [999, 999, 0, 1], [4, 999, 999, 0]]

DSA Rust

fn floyd_warshall(mut dist: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = dist.len();
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if dist[i][k] != 999 && dist[k][j] != 999 {
                    let new_dist = dist[i][k] + dist[k][j];
                    if new_dist < dist[i][j] {
                        dist[i][j] = new_dist;
                    }
                }
            }
        }
    }
    dist
}

fn main() {
    let dist = vec![
        vec![0, 3, 8, 999],
        vec![999, 0, 2, 999],
        vec![999, 999, 0, 1],
        vec![4, 999, 999, 0],
    ];
    let result = floyd_warshall(dist);
    println!("{:?}", result);
}

A [[0, 3, 5, 7], [7, 0, 2, 3], [5, 8, 0, 1], [4, 7, 9, 0]]

B [[0, 3, 8, 9], [999, 0, 2, 3], [999, 999, 0, 1], [4, 7, 11, 0]]

C [[0, 3, 5, 6], [7, 0, 2, 3], [5, 8, 0, 1], [4, 7, 9, 0]]

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

💡 Hint

Trace the shortest paths through intermediate nodes step by step.

Option C correctly updates distances using intermediate nodes. For example, distance from 0 to 2 is updated from 8 to 5 via node 1 (0->1->2). Other options have incorrect distances or miss updates.

🧠 Conceptual

intermediate

Understanding Floyd Warshall Algorithm Complexity

What is the time complexity of the Floyd Warshall algorithm for a graph with n vertices?

A O(n^2)

B O(n^3)

C O(n log n)

D O(2^n)

💡 Hint

Consider the three nested loops over vertices.

Floyd Warshall uses three nested loops each running n times, resulting in O(n^3) time complexity.

🔧 Debug

advanced

Identify the error in this Floyd Warshall implementation

What error will this Rust code produce when running Floyd Warshall?

Code snippet:
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]; } } } }

DSA Rust

fn floyd_warshall(mut dist: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = dist.len();
    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];
                }
            }
        }
    }
    dist
}

A Logic error: does not check for infinity before addition

B Panic due to integer overflow when adding 999 + 999

C Compile error: missing semicolon after if condition

D No error, runs correctly

💡 Hint

Check what happens when dist[i][k] or dist[k][j] is 999 (infinity).

Adding distances without checking if either is infinity (999) can cause incorrect updates because 999 + 999 is not a valid path length.

❓ Predict Output

advanced

Detecting negative cycles with Floyd Warshall

After running Floyd Warshall on a graph, how can you detect if there is a negative cycle?

DSA Rust

fn has_negative_cycle(dist: &Vec<Vec<i32>>) -> bool {
    for i in 0..dist.len() {
        if dist[i][i] < 0 {
            return true;
        }
    }
    false
}

A Check if any element dist[i][j] is zero

B Check if any row sums to zero

C Check if any element dist[i][j] is greater than 999

D Check if any diagonal element dist[i][i] is negative

💡 Hint

Think about what a negative cycle means for distance from a node to itself.

A negative cycle causes the distance from a node to itself to become negative after Floyd Warshall completes.

🚀 Application

expert

Floyd Warshall with path reconstruction

Which code snippet correctly updates the path matrix to reconstruct shortest paths during Floyd Warshall?

DSA Rust

let mut dist = vec![vec![999; n]; n];
let mut next = vec![vec![None; n]; n];
// Initialization omitted
for k in 0..n {
    for i in 0..n {
        for j in 0..n {
            if dist[i][k] != 999 && dist[k][j] != 999 {
                let new_dist = dist[i][k] + dist[k][j];
                if new_dist < dist[i][j] {
                    dist[i][j] = new_dist;

A next[i][j] = next[i][k];

B next[i][j] = Some(k);

C next[i][j] = Some(j);

D next[i][j] = next[k][j];

💡 Hint

When updating dist[i][j], the next node on path from i to j is the next node on path from i to k.

To reconstruct the path, next[i][j] should point to the next node after i on the shortest path to j. When updating via k, this is next[i][k].

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