The floyd Warshall algorithm is used to find all pair shortest path with positive or negative edge wieghts (but with no (-)ve cycle)
The algorithm of flyod Warshall is based on Dynamic Programming solution
for(int k = 1 ; k <= N ; ++k ){
for(int i = 1 ; i <= N ; ++i ){
for(int j = 1 ; j <= N ; ++j {
dist[i][j] = min( dist[i][j] , dist[i][k] + dist[k][j] )
} } }
The complexity of the above code is O(N^3) , Hence its time complexity in all cases average , best , worst is O(N^3)
Space complexity : O(N^2)
Initially dist[i][j] = edge_weight ( if their is a edge from i to j )
if( no edge ) then
dist[i][j] = 0 ( i == j ) ( Self loop not present )
else
dist[i][j] = some_infinite_value ( you can take large value )
Now , let see how it works ,
shortest path between i to j is either edge_weight( i to j ) if edge is present or may be it involves atleast zero node in between them
May be shortest_path(i -> j ) is ( i ->x ->j ) equivalent to shortestpath ( i - > x ) + shortestpath ( x -> j )
Now same rule follows for ( i -> x ) and ( x - > j ) and so on....
This procedure repeats N times for each pair . That's why it is made up of three loops , two inner loop for all pairs , and outer for including all nodes between all pair : dist[i][k] + dist[k][j].
So complexity : O(N^3).
You can't reduce some iteration in the above code , without knowing anything related to graph , because you can't figure out without checking that which node gives shortest cost between (i->j ) that is ( i - > x - > j ) then 1 <= x <= N ( x can be anything ).