Floyd Warshall All Pairs Shortest Path in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance matrix with the given graph weights.

DSA Java

int[][] dist = new int[V][V];
for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
        if (i == j) {
            dist[i][j] = 0;
        } else if (graph[i][j] != 0) {
            dist[i][j] = graph[i][j];
        } else {
            dist[i][j] = [1];
        }
    }
}

Drag options to blanks, or click blank then click option'

AInteger.MAX_VALUE

B0

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of Integer.MAX_VALUE causes incorrect shortest path calculations.

Using negative values can cause wrong results in Floyd Warshall.

We use Integer.MAX_VALUE to represent no direct edge between nodes, meaning infinite distance.

2fill in blank

medium

Complete the code to update the distance matrix inside the triple nested loops.

DSA Java

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] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE && dist[i][k] + dist[k][j] < [1]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

AInteger.MAX_VALUE

Bdist[k][j]

Cdist[i][k]

Ddist[i][j]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with dist[i][k] or dist[k][j] instead of dist[i][j].

Using Integer.MAX_VALUE in the comparison causes logic errors.

The condition checks if the new path through k is shorter than the current distance dist[i][j].

3fill in blank

hard

Fix the error in the code that prints the final distance matrix after Floyd Warshall completes.

DSA Java

for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
        if (dist[i][j] == [1]) {
            System.out.print("INF ");
        } else {
            System.out.print(dist[i][j] + " ");
        }
    }
    System.out.println();
}

Drag options to blanks, or click blank then click option'

A0

BInteger.MAX_VALUE

Cnull

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of Integer.MAX_VALUE causes wrong output.

Using null causes compilation errors in Java.

Distances equal to Integer.MAX_VALUE mean no path exists, so print "INF".

4fill in blank

hard

Fill both blanks to complete the Floyd Warshall triple nested loops correctly.

DSA Java

for (int [1] = 0; [2] < V; [1]++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][[1]] != Integer.MAX_VALUE && dist[[1]][j] != Integer.MAX_VALUE && dist[i][[1]] + dist[[1]][j] < dist[i][j]) {
                dist[i][j] = dist[i][[1]] + dist[[1]][j];
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

Ak

Bj

Ci

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for the loop and inside the condition causes errors.

Using i or j instead of k for the intermediate vertex.

The outer loop variable is k, which is used as the intermediate vertex index.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension-like structure in Java to print shortest paths with conditions.

DSA Java

Map<Integer, Integer> shortestPaths = new HashMap<>();
for (int [1] = 0; [1] < V; [1]++) {
    if (dist[[1]][[2]] != Integer.MAX_VALUE && [3] != [1]) {
        shortestPaths.put([1], dist[[1]][[2]]);
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bj

Csource

Ddestination

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same variable for source and destination causes logic errors.

Using undefined variables causes compilation errors.

We iterate over i as source nodes, check distances to j as destination nodes, and ensure source and destination are not the same.

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