Please enable JavaScript.
Coggle requires JavaScript to display documents.
Floyd's Algorithm - Coggle Diagram
Floyd's Algorithm
Algorithm
Floyd(W[1..n, 1..n])
//Implements Floyd’s algorithm for the all-pairs shortest-paths problem
//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
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
D[i, j ] ← min{D[i, j ], D[i, k] + D[k, j ]}
return D
It is used to solve the all-pairs shortest-paths problem
Given a weighted connected graph (undirected or directed), the all-pairs shortest-paths
problem asks to find the distances from each vertex to all other vertices. This is one of several variations of the problem involving shortest paths in graph
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 called Floyd’s algorithm after its co-inventor Robert W. Floyd
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
In particular, the series starts with D(0), which does not allow
any intermediate vertices in its paths; hence D(0) is simply the weght of the matrix
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
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 and 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 of Floyd’s algorithm is cubic—as is the time
efficiency of Warshall’s algorithm