Floyd Warshall All Pairs Shortest Path in DSA Rust

Mental Model

We find the shortest paths between every pair of points by checking if going through a middle point is better than going directly.

Analogy: Imagine you want to travel between cities. Sometimes going through a third city is faster than going straight. We check all possible middle cities to find the quickest routes.

Graph with 4 nodes:
  (0)---5---(1)
   | \       |
   10  3     1
   |     \   |
  (3)---2---(2)

Distance matrix before:
[0, 5, 3, 10]
[∞, 0, 1, ∞]
[∞, ∞, 0, 2]
[∞, ∞, ∞, 0]

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0->1=5, 0->3=10, 0->2=3, 1->2=1, 2->3=2

Goal: Find shortest distances between every pair of nodes

Step 1: Initialize distance matrix with direct edges and 0 for self loops

[[0, 5, 3, 10],
 [∞, 0, 1, ∞],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: Start with known direct distances and zero for same node

Step 2: Use node 0 as intermediate: update distances if going through 0 is shorter

[[0, 5, 3, 10],
 [∞, 0, 1, ∞],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: No shorter paths found through node 0 at this step

Step 3: Use node 1 as intermediate: update distances if going through 1 is shorter

[[0, 5, 3, 10],
 [∞, 0, 1, ∞],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: No shorter paths found through node 1. For example, 0->1->2 = 5 + 1 = 6 > current 3

Step 4: Use node 2 as intermediate: update distances if going through 2 is shorter

[[0, 5, 3, 5],
 [∞, 0, 1, 3],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: 0->3 updated from 10 to 5 via 0->2->3 (3+2=5), 1->3 updated from ∞ to 3 via 1->2->3 (1+2=3)

Step 5: Use node 3 as intermediate: update distances if going through 3 is shorter

[[0, 5, 3, 5],
 [∞, 0, 1, 3],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Why: No shorter paths found through node 3 at this step

Result:

Final shortest path matrix:
[[0, 5, 3, 5],
 [∞, 0, 1, 3],
 [∞, ∞, 0, 2],
 [∞, ∞, ∞, 0]]

Annotated Code

DSA Rust

const INF: i32 = i32::MAX / 2; // large number to avoid overflow

fn floyd_warshall(graph: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = graph.len();
    let mut dist = graph.clone();

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]; // update if shorter path found
                }
            }
        }
    }
    dist
}

fn print_matrix(matrix: &Vec<Vec<i32>>) {
    for row in matrix {
        for &val in row {
            if val == INF {
                print!("∞ ");
            } else {
                print!("{} ", val);
            }
        }
        println!();
    }
}

fn main() {
    let graph = vec![
        vec![0, 5, 3, 10],
        vec![INF, 0, 1, INF],
        vec![INF, INF, 0, 2],
        vec![INF, INF, INF, 0],
    ];

    let shortest_paths = floyd_warshall(&graph);
    print_matrix(&shortest_paths);
}

for k in 0..n {

iterate over each node as intermediate point

for i in 0..n {

iterate over each source node

for j in 0..n {

iterate over each destination node

if dist[i][k] + dist[k][j] < dist[i][j] {

check if path through k is shorter than current known path

dist[i][j] = dist[i][k] + dist[k][j];

update shortest distance to new shorter path

Output

0 5 3 5 

∞ 0 1 3 

∞ ∞ 0 2 

∞ ∞ ∞ 0 

Complexity Analysis

Time: O(n^3) because we check all pairs of nodes for every possible intermediate node

Space: O(n^2) because we store distances between every pair of nodes

vs Alternative: Compared to running Dijkstra from each node (O(n * (E + V log V))), Floyd Warshall is simpler but slower for sparse graphs

Edge Cases

Graph with no edges except self loops

Distances remain zero for self loops and infinite for others

DSA Rust

if dist[i][k] + dist[k][j] < dist[i][j] {

Graph with negative edges but no negative cycles

Algorithm correctly finds shortest paths including negative edges

DSA Rust

if dist[i][k] + dist[k][j] < dist[i][j] {

Graph with negative cycle

Algorithm does not detect negative cycles; distances may become incorrect or decrease indefinitely

DSA Rust

No explicit guard; Floyd Warshall requires separate negative cycle detection

When to Use This Pattern

When asked to find shortest paths between all pairs of points in a graph, especially with possible negative edges, use Floyd Warshall because it systematically checks all intermediate nodes.

Common Mistakes

Mistake: Not initializing distances correctly with large values for no direct edges
Fix: Initialize missing edges with a large number (infinity) to represent no direct path

Mistake: Not checking if sum of distances overflows or is invalid
Fix: Use a large but safe number for infinity and avoid adding infinity to prevent overflow

Mistake: Forgetting to update distance when a shorter path is found
Fix: Update distance matrix inside the if condition when a shorter path is detected

Summary

Finds shortest paths between every pair of nodes by checking all possible intermediate nodes.

Use when you need all pairs shortest paths, including graphs with negative edges but no negative cycles.

The key insight is that any shortest path can be built by combining shorter paths through intermediate nodes.

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