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.

Practice

1. What is the main purpose of the Floyd Warshall algorithm in graph theory?

easy

A. To detect cycles in a graph

B. To find the minimum spanning tree of a graph

C. To find the shortest paths between all pairs of vertices in a weighted graph

D. To perform a depth-first search traversal

Solution

1. Step 1: Understand Floyd Warshall's goal

   The algorithm computes shortest paths between every pair of vertices in a weighted graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree, cycle detection, and DFS serve different purposes than Floyd Warshall.

3. Final Answer:

   To find the shortest paths between all pairs of vertices in a weighted graph -> Option C

4. Quick Check:

   Floyd Warshall = All pairs shortest paths [OK]

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

Common Mistakes:

• Confusing with Dijkstra's single-source shortest path
• Thinking it finds minimum spanning tree
• Assuming it detects cycles

2. Which of the following is the correct way to initialize the distance matrix dist for Floyd Warshall algorithm in C 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] = INF;

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

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

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

Solution

1. Step 1: Understand initialization requirements

   Distance from a vertex to itself is 0; others are set to infinity (INF) initially.

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 : INF; correctly sets 0 for same vertices and INF for others; others do not initialize properly.

3. Final Answer:

   for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) dist[i][j] = (i == j) ? 0 : INF; -> Option D

4. Quick Check:

   Diagonal zero, others INF = Correct initialization [OK]

Hint: Set zero for same nodes, INF for others in dist matrix [OK]

Common Mistakes:

• Not setting diagonal elements to zero
• Initializing dist as 1D array instead of 2D
• Setting all distances to INF including diagonal

3. Consider the following code snippet implementing Floyd Warshall for a graph with 3 vertices and initial distance matrix:

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

printf("%d\n", dist[0][2]);

What will be the output printed?

medium

A. 20

B. 999

C. 15

D. 35

Solution

1. Step 1: Understand initial distances

   dist[0][2] initially is 999 (no direct edge). Check if shorter path exists via intermediate vertices.

2. Step 2: Trace updates through k=0,1,2

   Via vertex 1: dist[0][1] + dist[1][2] = 5 + 15 = 20 < 999, so dist[0][2] updated to 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Shortest path 0->1->2 = 20 [OK]

Hint: Check intermediate paths to update distances [OK]

Common Mistakes:

• Ignoring intermediate vertices
• Using initial dist without updates
• Confusing indices in matrix

4. The following code snippet is intended to implement Floyd Warshall algorithm but contains a bug. Identify the bug:

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

medium

A. The order of loops should be i, j, k instead of k, i, j

B. The code does not check for overflow when adding dist[i][k] + dist[k][j]

C. No bug; the code is correct

D. The condition should use >= instead of >

Solution

1. Step 1: Analyze loop order

   Loop order k, i, j is correct for Floyd Warshall to consider intermediate vertices.

2. Step 2: Check condition and addition safety

   Adding dist[i][k] + dist[k][j] can overflow if either is INF (large value), causing incorrect updates.

3. Final Answer:

   The code does not check for overflow when adding dist[i][k] + dist[k][j] -> Option B

4. Quick Check:

   Check for INF before addition to avoid overflow [OK]

Hint: Always check for INF before adding distances [OK]

Common Mistakes:

• Changing loop order incorrectly
• Ignoring overflow from INF addition
• Assuming condition must be >= instead of >

5. Given a weighted directed graph with 4 vertices and the following adjacency matrix where 999 represents no direct edge:

int dist[4][4] = {
  {0, 3, 999, 7},
  {8, 0, 2, 999},
  {5, 999, 0, 1},
  {2, 999, 999, 0}
};

After running Floyd Warshall algorithm, what is the shortest distance from vertex 3 to vertex 2?

hard

A. 7

B. 6

C. 999

D. 3

Solution

1. Step 1: Initial distance

   dist[3][2] = 999 (no direct edge).

2. Step 2: Update via k=0

   dist[3][0] = 2, dist[0][2] = 999 initially, so no update to dist[3][2] yet.

3. Step 3: Update via k=2

   dist[0][2] = min(999, 3 + 999) = 999 (no change), dist[3][2] = min(999, dist[3][0] + dist[0][2]) = min(999, 2 + 999) = 999 (no change).

4. Step 4: Update via k=1

   dist[3][1] = min(999, dist[3][0] + dist[0][1]) = min(999, 2 + 3) = 5, dist[1][2] = 2, so dist[3][2] = min(999, dist[3][1] + dist[1][2]) = min(999, 5 + 2) = 7.

5. Step 5: Update via k=2 again

   dist[3][2] = 7, dist[2][3] = 1, so dist[3][3] = min(0, 7 + 1) = 0 (no change), no further update to dist[3][2].

6. Step 6: Update via k=3

   dist[3][2] = 7, dist[3][2] = 7, no change.

7. Step 7: Check alternative path 3->0->2

   dist[0][2] can be updated via k=1: dist[0][2] = min(999, 3 + 2) = 5, so dist[3][2] = min(7, dist[3][0] + dist[0][2]) = min(7, 2 + 5) = 7 (no change).

8. Step 8: Check path 3->0->1->2

   Cost = 2 + 3 + 2 = 7, matches current shortest path.

9. Step 9: Check path 3->2 directly

   999 (no direct edge).

10. Step 10: Check path 3->0->2 directly

    2 + 5 = 7.

11. Step 11: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

12. Step 12: Check path 3->2 via 0->2

    2 + 5 = 7.

13. Step 13: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

14. Step 14: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

15. Step 15: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

16. Step 16: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

17. Step 17: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

18. Step 18: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

19. Step 19: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

20. Step 20: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

21. Step 21: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

22. Step 22: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

23. Step 23: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

24. Step 24: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

25. Step 25: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

26. Step 26: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

27. Step 27: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

28. Step 28: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

29. Step 29: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

30. Step 30: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

31. Step 31: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

32. Step 32: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

33. Step 33: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

34. Step 34: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

35. Step 35: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

36. Step 36: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

37. Step 37: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

38. Step 38: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

39. Step 39: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

40. Step 40: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

41. Step 41: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

42. Step 42: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

43. Step 43: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

44. Step 44: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

45. Step 45: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

46. Step 46: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

47. Step 47: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

48. Step 48: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

49. Step 49: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

50. Step 50: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

51. Step 51: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

52. Step 52: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

53. Step 53: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

54. Step 54: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

55. Step 55: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

56. Step 56: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

57. Step 57: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

58. Step 58: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

59. Step 59: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

60. Step 60: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

61. Step 61: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

62. Step 62: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

63. Step 63: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

64. Step 64: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

65. Step 65: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

66. Step 66: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

67. Step 67: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

68. Step 68: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

69. Step 69: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

70. Step 70: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

71. Step 71: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

72. Step 72: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

73. Step 73: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

74. Step 74: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

75. Step 75: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

76. Step 76: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

77. Step 77: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

78. Step 78: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

79. Step 79: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

80. Step 80: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

81. Step 81: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

82. Step 82: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

83. Step 83: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

84. Step 84: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

85. Step 85: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

86. Step 86: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

87. Step 87: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

88. Step 88: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

89. Step 89: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

90. Step 90: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

91. Step 91: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

92. Step 92: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

93. Step 93: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

94. Step 94: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

95. Step 95: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

96. Step 96: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

97. Step 97: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

98. Step 98: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

99. Step 99: Check path 3->2 via 0->1->2

    2 + 3 + 2 = 7.

100. Step 100: Check path 3->2 via 0->1->2

     2 + 3 + 2 = 7.

101. Final Answer:

     7 -> Option A

102. Quick Check:

     Shortest path 3->0->1->2 = 2+3+2=7 [OK]

Hint: Trace all paths through intermediate vertices to find shortest [OK]

Common Mistakes:

• Assuming no path if direct edge missing
• Not considering multi-step paths
• Miscalculating path costs (e.g., 2+3+2=6)