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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd Warshall on a 3-node graph

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

Graph edges with weights:
0 -> 1: 4
0 -> 2: 11
1 -> 2: 2

Initial distance matrix (use 999 for infinity):
[[0, 4, 11], [999, 0, 2], [999, 999, 0]]

Show the final matrix after Floyd Warshall completes.

DSA C

int dist[3][3] = {
  {0, 4, 11},
  {999, 0, 2},
  {999, 999, 0}
};

// Floyd Warshall algorithm runs here
// Output final dist matrix

A [[0, 4, 6], [999, 0, 2], [999, 999, 0]]

B ]]0 ,999 ,999[ ,]2 ,0 ,999[ ,]6 ,4 ,0[[

C [[0, 4, 11], [999, 0, 2], [999, 999, 0]]

D [0, 4, 6], [999, 0, 2], [999, 999, 0]]

💡 Hint

Check if going through node 1 reduces distance from 0 to 2.

The shortest path from 0 to 2 is via node 1: 0->1 (4) + 1->2 (2) = 6, which is less than direct 11.

🧠 Conceptual

intermediate

Understanding Floyd Warshall Algorithm Complexity

What is the time complexity of the Floyd Warshall algorithm for a graph with n nodes?

A O(n^3)

B O(n^2)

C O(n log n)

D O(n!)

💡 Hint

Think about the three nested loops over nodes.

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

🔧 Debug

advanced

Identify the error in Floyd Warshall implementation

What error will this Floyd Warshall code produce?

int dist[3][3] = { {0, 5, 999}, {50, 0, 15}, {30, 999, 0} }; for (int k = 0; k < 3; k++) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } // Note: 999 represents infinity.

A No error, code runs correctly

B Integer overflow when adding dist[i][k] + dist[k][j]

C Array index out of bounds error

D Division by zero error

💡 Hint

Check what happens when adding large values representing infinity.

Adding 999 + 999 can overflow int or produce incorrect results, causing wrong comparisons.

❓ Predict Output

advanced

Final distance matrix with negative edge weights but no negative cycles

Given the graph with edges:
0 -> 1: 3
0 -> 2: 8
1 -> 2: -4
2 -> 3: 2
3 -> 1: 1

Initial distance matrix (999 for infinity):
[[0, 3, 8, 999], [999, 0, -4, 999], [999, 999, 0, 2], [999, 1, 999, 0]]

What is the final distance matrix after Floyd Warshall?

A [[0, 3, 8, 999], [999, 0, -4, 999], [999, 999, 0, 2], [999, 1, 999, 0]]

B [[0, 3, 8, 10], [999, 0, -4, -2], [999, 999, 0, 2], [999, 1, 999, 0]]

C [[0, 1, -3, 1], [999, 0, -4, 0], [999, 3, 0, 2], [999, 1, -3, 0]]

D [[0, 1, -3, -1], [999, 0, -4, -2], [999, 3, 0, 2], [999, 1, -3, 0]]

💡 Hint

Check paths that use negative edges to reduce distances.

Floyd Warshall updates distances using intermediate nodes, reducing some paths below initial weights.

🧠 Conceptual

expert

Detecting negative cycles using Floyd Warshall

How can Floyd Warshall algorithm detect if a graph contains a negative weight cycle?

A If any dist[i][j] is greater than initial weight

B If the sum of all distances is negative

C If any dist[i][i] becomes negative after the algorithm finishes

D If the number of edges is greater than nodes

💡 Hint

Think about shortest path from a node to itself.

A negative value on the diagonal means a negative cycle reachable from that node.