Floyd Warshall All Pairs Shortest Path in DSA Java

Mental Model

We find the shortest path between every pair of points by checking if going through a middle point is shorter than the direct path.

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

 0 -> 3 -> ∞
 ∞ -> 0 -> 1
 ∞ -> ∞ -> 0

(∞ means no direct path)

Dry Run Walkthrough

Input: Graph with 3 nodes and edges: 0->1=3, 1->2=1, 0->2=∞ (no direct edge)

Goal: Find shortest distances between all pairs of nodes

Step 1: Start with initial distance matrix from edges

0 -> 3 -> ∞
∞ -> 0 -> 1
∞ -> ∞ -> 0

Why: We need the base distances to improve upon

Step 2: Check if going through node 0 improves distances

0 -> 3 -> ∞
∞ -> 0 -> 1
∞ -> ∞ -> 0

Why: No improvements found using node 0 as middle

Step 3: Check if going through node 1 improves distances

0 -> 3 -> 4
∞ -> 0 -> 1
∞ -> ∞ -> 0

Why: Distance from 0 to 2 updated from ∞ to 4 via node 1

Step 4: Check if going through node 2 improves distances

0 -> 3 -> 4
∞ -> 0 -> 1
∞ -> ∞ -> 0

Why: No further improvements found using node 2

Result:

0 -> 3 -> 4
∞ -> 0 -> 1
∞ -> ∞ -> 0

Annotated Code

DSA Java

public class FloydWarshall {
    static final int INF = 99999;

    public static void floydWarshall(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];

        // Initialize distance matrix same as input graph
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // Update distances considering each node as intermediate
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    // If path i->k and k->j exists and is shorter, update i->j
                    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];
                    }
                }
            }
        }

        printSolution(dist);
    }

    public static void printSolution(int[][] dist) {
        int V = dist.length;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("∞ ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int INF = 99999;
        int[][] graph = {
            {0, 3, INF},
            {INF, 0, 1},
            {INF, INF, 0}
        };

        floydWarshall(graph);
    }
}

for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { dist[i][j] = graph[i][j]; } }

copy initial graph distances to dist matrix

for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { 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 dist[i][j] if going through k is shorter

Output

0 3 4 

∞ 0 1 

∞ ∞ 0 

Complexity Analysis

Time: O(V^3) because we check all pairs (i,j) for every intermediate node k

Space: O(V^2) because we store distances between all pairs in a matrix

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

Edge Cases

Graph with no edges except self loops

Distances remain 0 for same nodes and ∞ for others

DSA Java

if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])

Graph with negative edge weights but no negative cycles

Algorithm correctly finds shortest paths including negative edges

DSA Java

if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])

Graph with negative cycles

Algorithm does not detect negative cycles; distances may become incorrect

DSA Java

No explicit guard; Floyd Warshall needs extension to detect negative cycles

When to Use This Pattern

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

Common Mistakes

Mistake: Not checking if intermediate paths exist before adding distances, causing integer overflow
Fix: Add condition to ensure dist[i][k] and dist[k][j] are not INF before adding

Mistake: Using a large number for INF that causes overflow when added
Fix: Use a safe large number and check for INF before addition to avoid overflow

Summary

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

Use when you need all pairs shortest paths and graph may have negative edges but no negative cycles.

The key is to improve paths step-by-step by checking if going through each node is shorter.

Practice

1. What does the Floyd Warshall algorithm primarily compute in a graph?

easy

A. Shortest paths between all pairs of vertices

B. Minimum spanning tree of the graph

C. Depth-first traversal order

D. Maximum flow between two nodes

Solution

1. Step 1: Understand Floyd Warshall purpose

   The Floyd Warshall algorithm is designed to find shortest paths between every pair of vertices in a weighted graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree, depth-first traversal, and maximum flow solve different problems, not all pairs shortest paths.

3. Final Answer:

   Shortest paths between all pairs of vertices -> Option A

4. Quick Check:

   Floyd Warshall = All pairs shortest paths [OK]

Hint: Floyd Warshall = shortest paths for all vertex pairs [OK]

Common Mistakes:

• Confusing with Dijkstra's single-source shortest path
• Thinking it finds minimum spanning tree
• Mixing with traversal algorithms

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall in Java for a graph with V vertices?

easy

A. for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = (i == j) ? 0 : Integer.MAX_VALUE;

B. for (int i = 0; i < V; i++) dist[i] = new int[V];

C. dist = new int[V][V]; for (int i = 0; i < V; i++) dist[i][i] = 1;

D. for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = 0;

Solution

1. Step 1: Understand initialization needs

   Distance from a vertex to itself should be 0, and to others should be infinity (represented by Integer.MAX_VALUE).

2. Step 2: Check each option

   for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = (i == j) ? 0 : Integer.MAX_VALUE; correctly sets 0 for same vertices and max value for others. for (int i = 0; i < V; i++) dist[i] = new int[V]; only initializes array but not values. dist = new int[V][V]; for (int i = 0; i < V; i++) dist[i][i] = 1; sets diagonal to 1 incorrectly. for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = 0; sets all to 0, which is wrong.

3. Final Answer:

   for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = (i == j) ? 0 : Integer.MAX_VALUE; -> Option A

4. Quick Check:

   Initialize dist[i][i] = 0, others = infinity [OK]

Hint: Set zero for same nodes, max value for others [OK]

Common Mistakes:

• Not setting distance to self as zero
• Setting all distances to zero
• Forgetting to initialize the matrix fully

3. What will be the output distance matrix after running Floyd Warshall on this graph with 3 vertices and edges: 0->1=4, 1->2=3, 0->2=10?

int V = 3;
int[][] dist = {
  {0, 4, 10},
  {Integer.MAX_VALUE, 0, 3},
  {Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
};
// Floyd Warshall algorithm applied here

medium

A. [[0, 4, 3], [∞, 0, 3], [∞, ∞, 0]]

B. [[0, 4, 10], [∞, 0, 3], [∞, ∞, 0]]

C. [[0, 7, 10], [∞, 0, 3], [∞, ∞, 0]]

D. [[0, 4, 7], [∞, 0, 3], [∞, ∞, 0]]

Solution

1. Step 1: Initial distances

   Start with dist matrix: 0->1=4, 1->2=3, 0->2=10, others infinity or 0 on diagonal.

2. Step 2: Update using intermediate vertices

   Check if path 0->1->2 is shorter than 0->2 directly: 4 + 3 = 7 < 10, so update dist[0][2] = 7.

3. Final Answer:

   [[0, 4, 7], [∞, 0, 3], [∞, ∞, 0]] -> Option D

4. Quick Check:

   0->2 updated to 7 via 1 [OK]

Hint: Check if indirect path is shorter than direct [OK]

Common Mistakes:

• Not updating indirect shorter paths
• Confusing infinity with zero
• Ignoring intermediate vertex updates

4. Identify the bug in this Floyd Warshall code snippet:

for (int k = 0; k < V; k++) {
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

Assume dist uses Integer.MAX_VALUE for infinity.

medium

A. Missing initialization of dist matrix

B. Loop variables are in wrong order

C. No check for Integer.MAX_VALUE before addition causing overflow

D. Should use '>' instead of '<' in if condition

Solution

1. Step 1: Understand addition with infinity

   Adding Integer.MAX_VALUE + any positive number causes overflow and incorrect results.

2. Step 2: Check code for safety

   Code lacks checks to ensure dist[i][k] and dist[k][j] are not Integer.MAX_VALUE before adding.

3. Final Answer:

   No check for Integer.MAX_VALUE 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 Integer.MAX_VALUE + number
• Assuming loops order causes error
• Confusing comparison operator direction

5. Given a graph with 4 vertices and edges:
0->1=5, 0->3=10, 1->2=3, 2->3=1
Use Floyd Warshall to find the shortest distance from vertex 0 to 3 after all updates.
What is the shortest distance from 0 to 3?

hard

A. 10

B. 9

C. 8

D. 7

Solution

1. Step 1: Initial distances

   Direct edges: 0->1=5, 0->3=10, 1->2=3, 2->3=1. Other distances are infinity or 0 on diagonal.

2. Step 2: Check indirect paths

   Path 0->1->2->3 distance = 5 + 3 + 1 = 9, which is less than direct 0->3=10, so update shortest distance to 9.

3. Final Answer:

   9 -> Option B

4. Quick Check:

   0->1->2->3 = 9 < 10 [OK]

Hint: Sum edges along path to find shortest distance [OK]

Common Mistakes:

• Ignoring multi-step paths
• Choosing direct edge without checking alternatives
• Adding edges incorrectly