Complexity Analysis of Floyd Warshall Algorithm
- Time Complexity: O(V3), where V is the number of vertices in the graph and we run three nested loops each of size V
- Auxiliary Space: O(V2), to create a 2-D matrix in order to store the shortest distance for each pair of nodes.
Floyd-Warshall Algorithm in Python
The Floyd-Warshall algorithm, named after its creators Robert Floyd and Stephen Warshall, is fundamental in computer science and graph theory. It is used to find the shortest paths between all pairs of nodes in a weighted graph. This algorithm is highly efficient and can handle graphs with both positive and negative edge weights, making it a versatile tool for solving a wide range of network and connectivity problems.
The Floyd Warshall Algorithm is an all-pair shortest path algorithm, unlike Dijkstra and Bellman-Ford which are single source shortest path algorithms. This algorithm works for both the directed and undirected weighted graphs. However, it does not work for the graphs with negative cycles (where the sum of the edges in a cycle is negative). It follows the Dynamic Programming approach to check every possible path going via every possible node to calculate the shortest distance between every pair of nodes.