Floyd–Warshall algorithm

In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation R {displaystyle R} , or (in connection with the Schulze voting system) widest paths between all pairs of vertices in a weighted graph. In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation R {displaystyle R} , or (in connection with the Schulze voting system) widest paths between all pairs of vertices in a weighted graph. The Floyd–Warshall algorithm is an example of dynamic programming, and was published in its currently recognized form by Robert Floyd in 1962. However, it is essentially the same as algorithms previously published by Bernard Roy in 1959 and also by Stephen Warshall in 1962 for finding the transitive closure of a graph, and is closely related to Kleene's algorithm (published in 1956) for converting a deterministic finite automaton into a regular expression. The modern formulation of the algorithm as three nested for-loops was first described by Peter Ingerman, also in 1962. The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with Θ ( | V | 3 ) {displaystyle Theta (|V|^{3})} comparisons in a graph, even though there may be up to Ω ( | V | 2 ) {displaystyle Omega (|V|^{2})} edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal. Consider a graph G {displaystyle G} with vertices V {displaystyle V} numbered 1 through  N {displaystyle N} . Further consider a function s h o r t e s t P a t h ( i , j , k ) {displaystyle mathrm {shortestPath} (i,j,k)} that returns the shortest possible path from i {displaystyle i} to j {displaystyle j} using vertices only from the set { 1 , 2 , … , k } {displaystyle {1,2,ldots ,k}} as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each i {displaystyle i} to each j {displaystyle j} using only vertices in { 1 , 2 , … , N } {displaystyle {1,2,ldots ,N}} . For each of these pairs of vertices, the s h o r t e s t P a t h ( i , j , k ) {displaystyle mathrm {shortestPath} (i,j,k)} could be either