Floyd–Warshall algorithm

The algorithm of Floyd and Warshall (also Floyd - Warshall algorithm or triple ) algorithm, named after Robert Floyd and Stephen Warshall, is an algorithm in graph theory. In Floyd's version it finds the shortest paths between all pairs of nodes of a graph and calculates the length ( APSP, all- pairs shortest path ). In Wars Hall's version, he finds the transitive closure of a graph. Both versions were introduced in 1962 and go back to an algorithm that Stephen Kleene in 1956 published in connection with regular expressions.

Description

The Floyd - Warshall algorithm is based on the principle of dynamic programming.

The Floyd algorithm is based on the following observation:

If the shortest path from u to v by w, then the partial paths are included from u to w and from w to v already minimal. So if we assume, you already know the shortest paths between all pairs of nodes that lead less than k only node with index and one seeks all shortest paths via nodes with index at most k, then there is a path from u to v in two ways Either he goes through node k, then it is composed of already known paths from u to k and from k to v, or is it the already known path from u to v via node with index less than k

Suppose the graph is given by its weight matrix w.

W [i, j] is the weight of the edge from i to j, if such an edge exists. If there is no edge from i to j w [i, j] is infinity.

Then one can determine the matrix of the shortest distances d by the following procedure:

Algorithm of Floyd ( 1) For all i, j: d [i, j] = w [i, j] (2) For k = 1 to n ( 3) For all pairs i, j (4) d [ i, j] = min ( d [ i, j], d [i, k] d [k, j]) If you want to calculate the transitive closure, changing the algorithm as follows:

W is the adjacency matrix, that is, w [i, j] is 1 if there is an edge from i to j, 0 if there is no edge exists.

The matrix d is calculated such that D [i, j] = 1, if and when a path exists from i to j:

Algorithm of Warshall (1) For k = 1 to n (2) For i = 1 to n (3) If d [i, k] = 1 (4) for j = 1 to n (5) If d [k, j] = 1: d [i, j ] = 1 In line ( 5) d [i, j] is set to 1 if and only if a path from i to k and from k to j, a path over edges index exists less than k.

The Floyd algorithm works even when the edges have negative weight. Cycles with negative length (unlike the Bellman - Ford algorithm ) but not detected and lead to a false result. Visible are negative cycles, but in hindsight by negative values ​​on the diagonal of the distance matrix.

The complexity of the Floyd - Warshall algorithm is, as the number of pairs is quadratic limited.

Other methods for the calculation of shortest paths

• Min -plus matrix multiplication algorithm
• A * algorithm
• Dijkstra algorithm
• Bellman - Ford algorithm