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 formula_1, 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 formula_2 comparisons in a graph, even though there may be up to formula_3 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 formula_4 with vertices formula_5 numbered 1 through formula_6. Further consider a function formula_7 that returns the shortest possible path from formula_8 to formula_9 using vertices only from the set formula_10 as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each formula_8 to each formula_9 using "any" vertex in formula_13. For each of these pairs of vertices, the formula_7 could be either  or  We know that the best path from formula_8 to formula_9 that only uses vertices formula_25 through formula_26 is defined by formula_27, and it is clear that if there was a better path from formula_8 to formula_15 to formula_9, then the length of this path would be the concatenation of the shortest path from formula_8 to formula_15 (only using intermediate vertices in formula_16) and the shortest path from formula_15 to formula_9 (only using intermediate vertices in formula_16).