Analysis Of Flloyd Warshal Algorithm

Question

I have seen many varients of complexities using diferent data structures in implementing Flloyd Warshal Algorithm.  Can you pls post standard algorithm and tells me in details how to derive the complexities.  Please also mention the variations possibles when data structure changes and How will effect the complexity taking Best case and Worst case senarios .

Comments

@vipsharmavip SIR Here is the question 

Answer 1

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 ).