The Floyd-Warshall Algorithm

1) This algorithm is for solving all pairs shortest paths problem on a directed graph G=(V,E)
2) It uses Dynamic Programming Approach
3) It runs in O(V^3)
4)Negative-weight edges may be present but Negative-weight cycles cannot present
5)The Floyd-Warshall algorithm exploits a relationship between path p and shortest paths from i to j with all intermediate vertices in the set{1,2,.....,k-1}.The relationship depends on wether or not k is an intermediate vertex of path p:
a)If k is not an intermediate vertex of path p,then all intermediate vertices of path p are in the set{1,2,.....k-1}. Thus,a shortest path from vertex i to vertex j with all intermediate vertices in the set{1,2,....,k-1} is also a shortest path from i to j with all intermediate vertices in the set{1,2,....,k}
b)If k is an intermediate vertex of path p,then we break p down into i->(p1)k->(p2)j.
Floyd warshall Algorithm

Floyd-Warshall(W){
          n <- rows[W]
          D^(0) <- W
          for(k<-1 to n)
          {
                   for(i<-1 to n){
                         for(j <- 1 to n){
                              d(subscript)ij(superscript)k = min(d(subscript)ik(superscript)(k-1) + d(subscript)kj(superscript)(k-1));
                         }
                   }
           }
}