What is the Floyd Warshall Algorithm?
Floyd Warshall algorithm is all pair shortest path algorithm. The Floyd Warshall algorithm is used to find out shortest path algorithm just like Dijkstra and Bellman-Ford algorithm. But the algorithm considered all pairs. The algorithm is easy to implement than the Dijkstra and Bellman-Ford algorithm. For this reason, it is far better than other shortest path algorithm.
The time complexity of the Floyd Warshall algorithm
According to the algorithm, to find the weight of a node we need to run three for loops for further calculation. The main condition code of the Floyd Warshall algorithm is given below,
for ( int k = 1; k <= n; k++)
{
for ( int i = 1; i <= n; i++)
{
for ( int j = 1; j <= n; j++)
{
if (w[i] [j] > w[i] [k] + w[k] [j])
}
}
}
As we see from the above code, the elements of the n length array need to run thrice a time to fulfill the condition. The big O notation is used to describe the time complexity of an algorithm where large input size matter to the time complexity. Please read the post for why do we need to use Big O notation. From the above code, we can write now,
Time Complexity = O ( k-th elements for n times ) * O ( i-th elements for n times ) * O ( j-th elements for n times )
= O (n) * O (n) * O (n)
= O (n * n * n)
= O (n3)
Finally, the time complexity of the Floyd Warshall algorithm is O (n3).
The Dijkstra algorithm can be applied for the all-pair shortest path but it is unable to find the negative cycle. If one's applied the Dijkstra algorithm for solving all shortest paths, then the time complexity will be O (nm log n).
Read Similar Posts:
1. Bellman ford algorithm time complexity
2. Dijkstra algorithm time complexity