Floyd Warshall All Pairs Shortest Path in DSA Rust - Build from Scratch

Floyd Warshall All Pairs Shortest Path

📖 Scenario: You are working as a city planner. You have a map of cities connected by roads with distances. You want to find the shortest distance between every pair of cities to plan efficient routes.

🎯 Goal: Build a program using the Floyd Warshall algorithm to find the shortest paths between all pairs of cities.

📋 What You'll Learn

Create a 2D matrix representing distances between cities

Add a variable for the number of cities

Implement the Floyd Warshall algorithm to update shortest distances

Print the final shortest distance matrix

💡 Why This Matters

🌍 Real World

City planners and GPS systems use all pairs shortest path algorithms to find the best routes between locations.

💼 Career

Understanding Floyd Warshall helps in roles involving route optimization, network analysis, and graph algorithms.

1

Create the distance matrix

Create a 2D vector called dist with these exact values representing distances between 4 cities:
vec![
vec![0, 5, 999, 10],
vec![999, 0, 3, 999],
vec![999, 999, 0, 1],
vec![999, 999, 999, 0]
]
Use 999 to represent no direct path.

DSA Rust

# Create the distance matrix called dist
# Your code here

Hint

Use vec![vec![...], vec![...], ...] to create a 2D vector.

2

Add the number of cities variable

Add a variable called n and set it to the number of cities, which is 4.

DSA Rust

fn main() {
    let mut dist = vec![
        vec![0, 5, 999, 10],
        vec![999, 0, 3, 999],
        vec![999, 999, 0, 1],
        vec![999, 999, 999, 0],
    ];
    // Add variable n for number of cities
    // Your code here
}

Hint

Use let n = 4; to store the number of cities.

3

Implement the Floyd Warshall algorithm

Use three nested for loops with variables k, i, and j from 0 to n (exclusive). Inside, update dist[i][j] to the minimum of dist[i][j] and dist[i][k] + dist[k][j].

DSA Rust

fn main() {
    let mut dist = vec![
        vec![0, 5, 999, 10],
        vec![999, 0, 3, 999],
        vec![999, 999, 0, 1],
        vec![999, 999, 999, 0],
    ];
    let n = 4;
    // Implement Floyd Warshall algorithm
    // Your code here
}

Hint

Use for k in 0..n, for i in 0..n, and for j in 0..n loops. Update dist[i][j] if a shorter path is found.

4

Print the shortest distance matrix

Use a for loop with variable i from 0 to n (exclusive). Inside, print the dist[i] vector.

DSA Rust

fn main() {
    let mut dist = vec![
        vec![0, 5, 999, 10],
        vec![999, 0, 3, 999],
        vec![999, 999, 0, 1],
        vec![999, 999, 999, 0],
    ];
    let n = 4;
    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];
                }
            }
        }
    }
    // Print the shortest distance matrix
    // Your code here
}

Hint

Use println!("{:?}", dist[i]) inside a loop to print each row.

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