Q10Design and Analysis of Algorithms
Question
2 marks
What is Floyd-Warshall Algorithm?
Answer
Floyd-Warshall Algorithm finds shortest paths between all pairs of vertices in a weighted graph, including negative edges (but no negative cycles).
The Floyd-Warshall Algorithm is a dynamic programming algorithm that computes shortest paths between every pair of vertices in a weighted directed graph. It handles negative edge weights but not negative cycles. Time Complexity: O(V³), Space: O(V²).
It works by iteratively improving the shortest path estimate between every pair (i, j) by considering each vertex k as an intermediate vertex: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each k from 1 to V. After considering all intermediate vertices, dist[i][j] holds the shortest path length.