The Floyd-Warshall algorithm follows the dynamic programming approach. It solves the all-pairs shortest path problem by breaking it down into smaller subproblems and combining their solutions in a bottom-up manner.
Key points about the approach:
- The algorithm maintains a matrix where each entry represents the shortest distance between a pair of vertices.
- It iteratively updates this matrix by considering each vertex as an intermediate point (pivot) to potentially shorten the path between two other vertices.
- For each vertex kkk, it checks if the path from iii to jjj can be improved by going through kkk, using the formula:
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\text{dist}[i][j]=\min(\text{dist}[i][j],\text{dist}[i][k]+\text{dist}[k][j])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
- This process is repeated for all vertices kkk, gradually improving the estimate of the shortest paths until the final matrix contains the shortest distances between all pairs.
- The approach uses three nested loops, resulting in a time complexity of O(n3)O(n^3)O(n3), where nnn is the number of vertices.
Thus, the algorithm systematically explores all possible intermediate vertices to find the shortest paths, leveraging dynamic programming's principle of solving overlapping subproblems and building up solutions incrementally
