Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________

The Floyd-Warshall algorithm is designed to find the shortest paths between all pairs of vertices in a weighted graph. It systematically considers all possible paths through the graph and updates the shortest distances accordingly.

Time Complexity

1. Algorithm Overview: The algorithm uses a dynamic programming approach, where it progressively improves the shortest paths by iterating through all vertices.

2. Iterations: The algorithm requires three nested loops, each iterating over the number of vertices $V$:

   • The outer loop iterates over each vertex as an intermediate point.
   • The two inner loops iterate over pairs of vertices to update their shortest paths.

3. Computational Complexity: For each pair of vertices, the algorithm checks whether including an intermediate vertex improves the shortest path. Therefore, the time complexity can be expressed as:

   $O(V^3)$

Final Answer

The time complexity of the Floyd-Warshall algorithm is $O(V^3)$, where $V$ is the number of vertices in the graph.