Bird
Raised Fist0
DSA Cprogramming~30 mins

Floyd Warshall All Pairs Shortest Path in DSA C - Build from Scratch

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Floyd Warshall All Pairs Shortest Path
📖 Scenario: You are working with a network of cities connected by roads. Each road has a travel cost. You want to find the shortest travel cost between every pair of cities.
🎯 Goal: Build a program that uses the Floyd Warshall algorithm to find the shortest paths between all pairs of cities in a given network.
📋 What You'll Learn
Create a 2D array called graph representing the travel costs between 4 cities.
Create an integer variable V for the number of cities.
Implement the Floyd Warshall algorithm using nested loops with variables k, i, and j.
Print the final shortest path matrix after running the algorithm.
💡 Why This Matters
🌍 Real World
Finding shortest travel costs between all pairs of cities helps in planning efficient routes for delivery, travel, or communication networks.
💼 Career
Understanding Floyd Warshall algorithm is useful for software engineers working on network routing, map services, and optimization problems.
Progress0 / 4 steps
1
Create the graph matrix
Create a 2D integer array called graph with 4 rows and 4 columns. Initialize it with these exact values: { {0, 5, 999, 10}, {999, 0, 3, 999}, {999, 999, 0, 1}, {999, 999, 999, 0} }. Also create an integer variable V and set it to 4.
DSA C
Hint

Use a 2D array to represent the graph. Use 999 to represent no direct path.

2
Set up the distance matrix
Create a 2D integer array called dist with 4 rows and 4 columns. Copy the values from graph into dist using nested for loops with variables i and j.
DSA C
Hint

Use two nested loops to copy each element from graph to dist.

3
Implement the Floyd Warshall algorithm
Use three nested for loops with variables k, i, and j to update dist[i][j] with the minimum of its current value and the sum of dist[i][k] and dist[k][j].
DSA C
Hint

Use three nested loops to check if going through city k gives a shorter path from i to j.

4
Print the shortest path matrix
Use nested for loops with variables i and j to print the dist matrix. Print each value followed by a space. Print a new line after each row. If the value is 999, print INF instead.
DSA C
Hint

Print each row of the dist matrix. Replace 999 with INF to show no path.

Practice

(1/5)
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)
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard