Why Floyd Warshall All Pairs Shortest Path in DSA Rust?

The Big Idea

Discover how a simple triple loop can solve the complex puzzle of shortest paths between every pair of points!

The Scenario

Imagine you have a map of cities connected by roads. You want to find the shortest path between every pair of cities. Doing this by checking each pair one by one and trying all possible routes by hand would be overwhelming and confusing.

The Problem

Manually checking all paths between every pair of cities is slow and prone to mistakes. You might miss a shorter route or waste time repeating the same checks. As the number of cities grows, the work becomes impossible to handle without a clear method.

The Solution

The Floyd Warshall algorithm solves this by systematically updating the shortest paths between all pairs of cities using a simple rule. It checks if going through an intermediate city offers a shorter route and updates the distances efficiently, covering all pairs at once.

Before vs After

✗ Before

for each city A:
  for each city B:
    find all routes from A to B
    choose shortest route

✓ After

for k in cities:
  for i in cities:
    for j in cities:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

What It Enables

This algorithm lets you quickly find the shortest paths between all pairs of points in a network, enabling fast decisions and route planning for complex systems.

Real Life Example

In a delivery company, Floyd Warshall helps find the quickest routes between every warehouse and customer location, saving time and fuel by planning all routes at once.

Key Takeaways

Manual path checking is slow and error-prone.

Floyd Warshall updates shortest paths using intermediate points efficiently.

It finds shortest paths between all pairs in one go.

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