Floyd Warshall All Pairs Shortest Path in DSA Java - 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 the best routes.

🎯 Goal: Build a program that uses the Floyd Warshall algorithm to find the shortest distances between all pairs of cities.

📋 What You'll Learn

Create a 2D array called graph with exact distances between 4 cities

Create a variable V for the number of cities

Implement the Floyd Warshall algorithm using nested for loops with variables k, i, and j

Print the final shortest distance matrix with proper formatting

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding Floyd Warshall helps in roles involving route optimization, network analysis, and logistics planning.

1

Create the initial graph matrix

Create a 2D integer array called graph with these exact values representing distances between 4 cities:
graph = new int[][] { {0, 5, 999, 10}, {999, 0, 3, 999}, {999, 999, 0, 1}, {999, 999, 999, 0} };
Use 999 to represent no direct path.

DSA Java

// Your code here

Hint

Use int[][] graph = new int[][] { ... }; to create the matrix with exact values.

2

Add the number of vertices variable

Create an integer variable called V and set it to the number of cities, which is 4.

DSA Java

public class FloydWarshall {
    public static void main(String[] args) {
        int[][] graph = new int[][] {
            {0, 5, 999, 10},
            {999, 0, 3, 999},
            {999, 999, 0, 1},
            {999, 999, 999, 0}
        };
        // Your code here
    }
}

Hint

Count the number of cities (rows) in the graph and assign it to V.

3

Implement the Floyd Warshall algorithm

Use three nested for loops with variables k, i, and j to update the graph matrix with shortest distances. Inside the innermost loop, update graph[i][j] to the minimum of its current value and graph[i][k] + graph[k][j].

DSA Java

public class FloydWarshall {
    public static void main(String[] args) {
        int[][] graph = new int[][] {
            {0, 5, 999, 10},
            {999, 0, 3, 999},
            {999, 999, 0, 1},
            {999, 999, 999, 0}
        };
        int V = 4;
        // Use nested for loops with k, i, j to update graph
        // Your code here
    }
}

Hint

Use three nested loops and update graph[i][j] if a shorter path is found through k.

4

Print the shortest distance matrix

Use nested for loops with variables i and j to print the graph matrix after running Floyd Warshall. Print graph[i][j] followed by a space. If the value is 999, print INF instead. Print a new line after each row.

DSA Java

public class FloydWarshall {
    public static void main(String[] args) {
        int[][] graph = new int[][] {
            {0, 5, 999, 10},
            {999, 0, 3, 999},
            {999, 999, 0, 1},
            {999, 999, 999, 0}
        };
        int V = 4;
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (graph[i][k] + graph[k][j] < graph[i][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
        // Print the shortest distance matrix
        // Your code here
    }
}

Hint

Use nested loops to print each element. Print INF if the value is 999.

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