Please enable JavaScript.
Coggle requires JavaScript to display documents.
Floyd's Algorithm, , image - Coggle Diagram
Floyd's Algorithm
-
-
-
-
-
Each of these matrices contains the lengths of shortest paths with certain constraints on the paths considered for the matrix in question. Specifically, the element d(k)
ij in the ith row and the j th column of matrix D(k) (i, j = 1, 2, . . . , n,
k = 0, 1, . . . , n) is equal to the length of the shortest path among all paths from
the ith vertex to the j th vertex with each intermediate vertex, if any, numbered
not higher than k. In particular, the series starts with D(0)
-
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 nothingother than the distance matrix being sought.
pseudocode
-
-
-
-
-
-
-
D[i, j ] ← min{D[i, j ], D[i, k] + D[k, j ]}
-
-
-
-
-
-
-
