Floyd Warshall All Pairs Shortest Path in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of the Floyd Warshall algorithm?

It finds the shortest paths between all pairs of nodes in a weighted graph, including graphs with negative edge weights but no negative cycles.

beginner

What is the time complexity of the Floyd Warshall algorithm?

The time complexity is O(V³), where V is the number of vertices in the graph.

intermediate

In Floyd Warshall, what does the matrix entry dist[i][j] represent during the algorithm?

It represents the shortest known distance from node i to node j considering intermediate nodes up to a certain index k.

intermediate

Why can Floyd Warshall handle negative edge weights but not negative cycles?

Because it updates shortest paths by checking intermediate nodes, but if a negative cycle exists, distances can decrease indefinitely, making shortest paths undefined.

beginner

What is the initial setup of the distance matrix in Floyd Warshall?

Set dist[i][j] to the edge weight if there is an edge from i to j; set dist[i][i] to 0 for all i; set dist[i][j] to infinity if no direct edge exists.

What does Floyd Warshall algorithm compute?

A Minimum spanning tree

B Shortest path from a single source to all vertices

C Shortest paths between all pairs of vertices

D Topological sort

Floyd Warshall computes shortest paths between every pair of vertices.

What is the time complexity of Floyd Warshall algorithm for a graph with V vertices?

A O(V²)

B O(V³)

C O(E log V)

D O(V + E)

Floyd Warshall uses three nested loops over vertices, resulting in O(V³) time.

Which type of graphs can Floyd Warshall handle that Dijkstra's algorithm cannot?

A Graphs with negative edge weights

B Graphs with cycles

C Graphs with only positive weights

D Graphs without edges

Floyd Warshall can handle negative edge weights as long as there are no negative cycles.

What does the Floyd Warshall algorithm use to update shortest paths?

A Relaxation of edges

B Depth-first search

C Greedy selection of edges

D Dynamic programming with intermediate nodes

It uses dynamic programming considering intermediate nodes to update shortest paths.

What is the initial value of dist[i][i] in Floyd Warshall algorithm?

A 0

B Edge weight from i to i

C Infinity

D -1

Distance from a node to itself is always 0.

Explain how the Floyd Warshall algorithm updates the shortest path matrix step-by-step.

Think about how the algorithm tries all possible intermediate nodes.

Describe the differences between Floyd Warshall and Dijkstra's algorithm in terms of use cases and limitations.

Consider the type of graphs and the problem each algorithm solves.

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)