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));
                         }
                   }
           }
}

B-Trees

1)In a B-tree of order m,each internal node except the root and the leaves has ceiling(m/2) to m nodes.
2)the number is called the branching factor of the Tree.
3)Let n denote total number of keys,p total number  of nodes of B-Tree of branching factor(order) of m
then p=n/(m-1) since each nodes of T contains (m - 1)keys;
4)there are m^k nodes on level k;
so, (p total number  of nodes) = 1 + m^2 +m^3+m^4+.......+m^k;
5)p = (m^(k+1) - 1)/(m-1) = n/(m-1);
=>m^(k + 1) - 1 = n
=>m^(k + 1) = n+1
=>k = logm(n+1) - 1;

5)The use of  trees with high branching factors makes sense when we store the tree nodes on external memory devices with slow access times,such as disks and drums.