Floyd Warshall All Pairs Shortest Path in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance matrix with the input graph.

DSA Rust

let mut dist = graph.clone();
for i in 0..n {
    for j in 0..n {
        if i != j && dist[i][j] == 0 {
            dist[i][j] = [1];
        }
    }
}

Drag options to blanks, or click blank then click option'

A0

Busize::MAX

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of a large number causes incorrect shortest path calculations.

Using negative numbers is invalid for unsigned types.

We use usize::MAX to represent infinity for unreachable paths initially.

2fill in blank

medium

Complete the code to update the distance matrix inside the triple nested loops.

DSA Rust

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

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Dusize::MAX

Attempts:

3 left

💡 Hint

Common Mistakes

Not checking for infinity causes overflow errors.

Using 0 or negative numbers for infinity check is incorrect.

We check if paths are not infinite before adding to avoid overflow.

3fill in blank

hard

Fix the error in the code to correctly print the shortest path matrix after computation.

DSA Rust

for i in 0..n {
    for j in 0..n {
        if dist[i][j] == [1] {
            print!("INF ");
        } else {
            print!("{} ", dist[i][j]);
        }
    }
    println!();
}

Drag options to blanks, or click blank then click option'

Ausize::MAX

B-1

C0

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Printing 0 or negative numbers instead of "INF" confuses output.

Using None causes compile errors in Rust.

We print "INF" for distances that remain infinite (usize::MAX).

4fill in blank

hard

Fill both blanks to complete the condition that updates the distance matrix only if a shorter path is found.

DSA Rust

if dist[i][k] != [1] && dist[k][j] != [2] {
    let new_dist = dist[i][k] + dist[k][j];
    if new_dist < dist[i][j] {
        dist[i][j] = new_dist;
    }
}

Drag options to blanks, or click blank then click option'

Ausize::MAX

B0

C-1

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Checking only one distance leads to incorrect updates.

Using different constants causes logic errors.

We check both distances against infinity before adding to avoid overflow.

5fill in blank

hard

Fill all three blanks to complete the Rust function signature and return statement for Floyd Warshall.

DSA Rust

fn floyd_warshall([1]: [2]) -> Vec<Vec<usize>> {
    let n = graph.len();
    let mut dist = graph.clone();
    // initialization and loops here
    [3]
}

Drag options to blanks, or click blank then click option'

Agraph

Bdist

Cgraph.clone()

D&Vec<Vec<usize>>

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong parameter names or types causes compile errors.

Returning the input graph instead of the distance matrix is incorrect.

The function takes a reference to a 2D vector named graph and returns the distance matrix dist.

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