ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# Floyd-Warshall algorithm

In computer science, the Floyd-Warshall algorithm is an algorithm to solve the all pairs shortest path problem in a weighted, directed graph by multiplying an adjacency-matrix representation of the graph multiple times. The edges may have negative weights, but no negative weight cycles. The time complexity is θ(V3).

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 drawn 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.

Here is a pseudo-algorithm of the Floyd-Warshall algorithm:

W is a n-by-n matrix

```FW(W) {
n <- rows[W];
D0 <- W;
for k <- 1 to n
do for i <- 1 to n
do for j <- 1 to n
do dijk <- min(dijk-1, dikk-1+dkjk-1)
return Dn
}```

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.