Editing Floyd–Warshall algorithm
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
The '''Floyd–Warshall algorithm''' finds [[Shortest_path#All-pairs_shortest_paths|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest_path#Single-source_shortest_paths|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement. | The '''Floyd–Warshall algorithm''' finds [[Shortest_path#All-pairs_shortest_paths|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest_path#Single-source_shortest_paths|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Theory of the algorithm== | ==Theory of the algorithm== |