Bird
Raised Fist0
DSA Cprogramming~5 mins

Floyd Warshall All Pairs Shortest Path in DSA C - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Floyd Warshall All Pairs Shortest Path
O(n³)
Understanding Time Complexity

We want to understand how the time needed grows when finding shortest paths between all pairs of points using Floyd Warshall.

How does the work increase as the number of points grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


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

This code updates shortest distances between all pairs of points by checking if going through an intermediate point is shorter.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: The triple nested loops that update distances.
  • How many times: Each loop runs n times, so the inner update runs n x n x n = n³ times.
How Execution Grows With Input

As the number of points n grows, the number of operations grows very fast because we check every pair through every possible intermediate point.

Input Size (n)Approx. Operations
101,000
1001,000,000
10001,000,000,000

Pattern observation: Operations grow roughly by the cube of n, so doubling n makes work about eight times bigger.

Final Time Complexity

Time Complexity: O(n³)

This means the time needed grows very quickly as the number of points increases, because we check all pairs through all intermediates.

Common Mistake

[X] Wrong: "Since there are only two loops inside, the time complexity is O(n²)."

[OK] Correct: There are actually three nested loops, each running n times, so the total work is n x n x n, which is O(n³).

Interview Connect

Understanding this cubic time complexity helps you explain why Floyd Warshall is good for small graphs but not for very large ones, showing your grasp of algorithm efficiency.

Self-Check

"What if we used a different algorithm that only checks edges instead of all pairs? How would the time complexity change?"

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