Why Floyd Warshall All Pairs Shortest Path in DSA C?

The Big Idea

Discover how a simple triple loop can solve the complex problem of finding shortest paths between every pair of points!

The Scenario

Imagine you have a map of cities connected by roads, and you want to find the shortest path between every pair of cities. Doing this by checking each pair one by one and trying all possible routes manually would be overwhelming and confusing.

The Problem

Manually checking all paths between every pair of cities is slow and error-prone because the number of possible routes grows very fast as cities increase. It's easy to miss shorter routes or get lost in complicated calculations.

The Solution

The Floyd Warshall algorithm solves this by systematically updating the shortest paths between all pairs of cities using a simple, repeated process. It checks if going through an intermediate city gives a shorter path, making the solution clear and efficient.

Before vs After

✗ Before

for each city A:
  for each city B:
    find all paths from A to B
    choose shortest path

✓ After

for k in cities:
  for i in cities:
    for j in cities:
      if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]

What It Enables

This algorithm enables finding shortest paths between all pairs of points quickly and reliably, even in complex networks.

Real Life Example

Navigation apps use this kind of algorithm to quickly find the best routes between any two locations on a map, considering all possible roads and connections.

Key Takeaways

Manual path checking is slow and confusing for many points.

Floyd Warshall uses a simple triple loop to update shortest paths.

It finds shortest paths between all pairs efficiently and clearly.

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)