SHPORA.net :: PDA

[ Back ]

Floyd-Warshall algorithm (sometimes known as the Roy-Floyd algorithm or Warshall's algorithm) is an algorithm for solving the all-pairs shortest path problem on weighted, directed graphs in cubic time.



Algorithm



The Floyd?Warshall algorithm takes as input an adjacency matrix representation of a weighted, directed graph (V, E). The weight of a path between two vertices is the sum of the weights of the edges along that path. The edges E of the graph may have negative weights, but the graph must not have any negative weight cycles. The algorithm computes, for each pair of vertices, the minimum weight among all paths between the two vertices. The running time complexity is Θ(n3). The algorithm is based on the following observation:



* Assuming the vertices of a directed graph G are V = {1, 2, 3, 4, ..., n}, consider a subset {1, 2, 3, ..., k}.

* For any pair of vertices i, j in V, consider all paths from i to j whose intermediate vertices are all taken from {1, 2, ..., k}, and p is a minimum weight path from among them.

* The 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 whether or not k is an intermediate vertex of path p.







Note that the pseudocode assumes the input graph is an adjacency matrix representation of a directed graph, with the value ∞ (infinity) as the weight between vertices which have no edge that directly connects them and 0 on the diagonal (distance from a vertex to itself)



function fw(int[1..n,1..n] graph) {



// Initialization



var int[1..n,1..n] dist := graph



var int[1..n,1..n] pred



for i from 1 to n



for j from 1 to n



pred[i,j] := nil



if (dist[i,j] > 0) and (dist[i,j] < Infinity)



pred[i,j] := i



// Main loop of the algorithm



for k from 1 to n



for i from 1 to n



for j from 1 to n



if dist[i,j] > dist[i,k] + dist[k,j]



dist[i,j] = dist[i,k] + dist[k,j]



pred[i,j] = pred[k,j]



return ( dist, pred ) // Tuple of the distance a