A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Class | All-pairs shortest path problem (for weighted graphs) |
---|---|
Data structure | Graph |
Worst-case performance | |
Best-case performance | |
Average performance | |
Worst-case space complexity |
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 directed weighted graph with positive or negative edge weights (but with no negative cycles).[1][2] 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 , or (in connection with the Schulze voting system) widest paths between all pairs of vertices in a weighted graph.
History and naming
The Floyd–Warshall algorithm is an example of dynamic programming, and was published in its currently recognized form by Robert Floyd in 1962.[3] However, it is essentially the same as algorithms previously published by Bernard Roy in 1959[4] and also by Stephen Warshall in 1962[5] for finding the transitive closure of a graph,[6] and is closely related to Kleene's algorithm (published in 1956) for converting a deterministic finite automaton into a regular expression.[7] The modern formulation of the algorithm as three nested for-loops was first described by Peter Ingerman, also in 1962.[8]
Algorithm
The Floyd–Warshall algorithm compares many possible paths through the graph between each pair of vertices. It is guaranteed to find all shortest paths and is able to do this with comparisons in a graph,[1][9] even though there may be edges in the graph. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal.
Consider a graph with vertices numbered 1 through . Further consider a function that returns the length of the shortest possible path (if one exists) from to using vertices only from the set as intermediate points along the way. Now, given this function, our goal is to find the length of the shortest path from each to each using any vertex in . By definition, this is the value , which we will find recursively.
Observe that must be less than or equal to : we have more flexibility if we are allowed to use the vertex . If is in fact less than , then there must be a path from to using the vertices that is shorter than any such path that does not use the vertex . Since there are no negative cycles this path can be decomposed as:
- (1) a path from to that uses the vertices , followed by
- (2) a path from to that uses the vertices .
And of course, these must be a shortest such path (or several of them), otherwise we could further decrease the length. In other words, we have arrived at the recursive formula:
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk