Floyd Warshall All Pairs Shortest Path in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd Warshall on a simple graph

What is the output distance matrix after running Floyd Warshall on this graph?

DSA Java

int INF = 99999;
int[][] graph = {
  {0, 5, INF, 10},
  {INF, 0, 3, INF},
  {INF, INF, 0, 1},
  {INF, INF, INF, 0}
};

int V = 4;
int[][] dist = new int[V][V];

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

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];
      }
    }
  }
}

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

A [[0, 5, 3, 4], [99999, 0, 3, 1], [99999, 99999, 0, 1], [99999, 99999, 99999, 0]]

B [[0, 5, 8, 10], [99999, 0, 3, 99999], [99999, 99999, 0, 1], [99999, 99999, 99999, 0]]

C [[0, 5, 8, 9], [99999, 0, 3, 4], [99999, 99999, 0, 1], [99999, 99999, 99999, 0]]

D [[0, 5, 8, 9], [99999, 0, 3, 99999], [99999, 99999, 0, 1], [99999, 99999, 99999, 0]]

💡 Hint

Trace the updates for each intermediate vertex k from 0 to 3.

The Floyd Warshall algorithm updates the shortest paths by considering each vertex as an intermediate point. The final matrix shows the shortest distances between all pairs. For example, the shortest path from vertex 0 to 3 is 9 (0->1->2->3).

🧠 Conceptual

intermediate

Understanding Floyd Warshall's time complexity

What is the time complexity of the Floyd Warshall algorithm for a graph with V vertices?

A O(V^2)

B O(V^3)

C O(V log V)

D O(V^2 log V)

💡 Hint

Consider the three nested loops over vertices.

Floyd Warshall uses three nested loops each running V times, resulting in O(V^3) time complexity.

🔧 Debug

advanced

Identify the bug in this Floyd Warshall implementation

What error will this code produce when run?

DSA Java

int INF = 99999;
int[][] graph = {
  {0, 3, INF},
  {2, 0, INF},
  {INF, 7, 0}
};
int V = 3;
int[][] dist = new int[V][V];

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

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];
      }
    }
  }
}

System.out.println(dist[0][2]);

A Prints 99999

B Prints 5

C Prints 10

D Throws ArrayIndexOutOfBoundsException

💡 Hint

Check if any path from 0 to 2 gets updated.

The distance from vertex 0 to 2 remains INF (99999) because no path exists connecting them through intermediate vertices.

❓ Predict Output

advanced

Detecting negative cycles with Floyd Warshall

What does the following code print after running Floyd Warshall on this graph?

DSA Java

int INF = 99999;
int[][] graph = {
  {0, 1, INF},
  {INF, 0, -1},
  {-1, INF, 0}
};
int V = 3;
int[][] dist = new int[V][V];

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

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];
      }
    }
  }
}

boolean hasNegativeCycle = false;
for (int i = 0; i < V; i++) {
  if (dist[i][i] < 0) {
    hasNegativeCycle = true;
    break;
  }
}

System.out.println(hasNegativeCycle);

A Compilation error

B false

C Runtime exception

D true

💡 Hint

Check the diagonal elements after the algorithm finishes.

A negative cycle exists if any diagonal element in the distance matrix becomes negative after Floyd Warshall completes. Here, it does.

🧠 Conceptual

expert

Why Floyd Warshall is preferred over repeated Dijkstra for dense graphs

Which reason best explains why Floyd Warshall is often preferred over running Dijkstra's algorithm from each vertex in dense graphs?

A Floyd Warshall can handle negative edge weights, while Dijkstra cannot, making it more versatile for dense graphs.

B Floyd Warshall has better time complexity for dense graphs because it runs in O(V^3), while repeated Dijkstra runs in O(V^2 log V).

C Floyd Warshall uses less memory than repeated Dijkstra for dense graphs.

D Floyd Warshall is easier to implement and always faster than Dijkstra regardless of graph density.

💡 Hint

Consider edge weights and algorithm limitations.

Floyd Warshall can handle negative edge weights and detect negative cycles, which Dijkstra cannot. This makes Floyd Warshall more suitable for dense graphs with such edges.

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