Please enable JavaScript.

Coggle requires JavaScript to display documents.

Floyd’s Algorithm, for k ← 1 to n do, for i ← 1 to n do, for j ← 1 to n do…

- - - - The distance between any two vertices in such a cycle can be made arbitrarily small by repeating the cycle enough times.
        
        The algorithm can be enhanced to find not only the lengths of the shortest paths for all vertex pairs but also the shortest paths themselves.
- - - - In particular, the series starts with D(0), which does not allow any intermediate vertices in its paths; hence, D(0) is simply the weight matrix of the graph.
        
        The last matrix in the series, D(n), contains the lengths of the shortest paths among all paths that can use all n vertices as intermediate and hence is nothing other than the distance matrix being sought.
- - - - We can partition all such paths into two disjoint subsets: those that do not use the kth vertex vk as intermediate and those that do.
        
        Since the paths of the first subset have their intermediate vertices numbered not higher than k − 1, he shortest of them is, by definition of our matrices, of length dij (k−1).
- - - - In other words, each of the paths is made up of a path from vi to vk with each intermediate vertex numbered not higher than k − 1 and a path from vk to vj with each intermediate vertex numbered not higher than k − 1.
- - - - The time efficiency of Floyd’s algorithm is cubic( Θ(n^3)) as is the time efficiency of Warshall’s algorithm.
- - - - //Input: The weight matrix W of a graph with no negative-length cycle
        
        //Output: The distance matrix of the shortest paths’ lengths
        
        D ← W //is not necessary if W can be overwritten