Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem

Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem

1. It is convenient to record the lengths of shortest paths in an n × n matrix D called the distance matrix

   • the element dij in the ith row and the jth column of this matrix indicates the length of the shortest path from the ith vertex to the jth vertex.
   • We can generate the distance matrix with an algorithm that is very similar to Warshall’s algorithm
     • It is applicable to both undirected and directed weighted graphs provided that they do not contain a cycle of a negative length.
       • 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

2. Floyd’s algorithm computes the distance matrix of a weighted graph with n vertices through a series of n × n matrices

   • Each of these matrices contains the lengths of shortest paths with certain constraints on the paths considered for the matrix in question.
     • 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, the shortest of them is, by definition of our matrices, of length dij(k−1
           • 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 length of the shortest path among the paths that use the kth vertex is equal to dik**(k−1) + dkj**(k−1)
             • the element in row i and column j of the current distance matrix D(k−1) is replaced by the sum of the elements in the same row i
               • the column k and in the same column j and the row k if and only if the latter sum is smaller than its current value.
   • The time efficiency is cubic.

Imagens e arquivos do mapa