Editing Floyd–Warshall algorithm (section)

==Comparison with other shortest path algorithms==
For graphs with non-negative edge weights, [[Dijkstra's algorithm]] can be used to find all shortest paths from a ''single'' vertex with running time <math>\Theta(|E| + |V| \log |V|)</math>. Thus, running Dijkstra starting at ''each'' vertex takes time <math>\Theta(|E||V| + |V|^2 \log |V|)</math>. Since <math>|E| = O(|V|^2)</math>, this yields a worst-case running time of repeated Dijkstra of <math>O(|V|^3)</math>. While this matches the asymptotic worst-case running time of the Floyd-Warshall algorithm, the constants involved matter quite a lot. When a [[dense graph|graph is dense]] (i.e., <math>|E| \approx |V|^2</math>), the Floyd-Warshall algorithm tends to perform better in practice. When the graph is sparse (i.e., <math>|E|</math> is significantly smaller than <math>|V|^2</math>), Dijkstra tends to dominate.

For sparse graphs with negative edges but no negative cycles, [[Johnson's algorithm]] can be used, with the same asymptotic running time as the repeated Dijkstra approach.

There are also known algorithms using [[fast matrix multiplication]] to speed up all-pairs shortest path computation in dense graphs, but these typically make extra assumptions on the edge weights (such as requiring them to be small integers).<ref>{{citation
 | last = Zwick | first = Uri | author-link = Uri Zwick
 | date = May 2002
 | doi = 10.1145/567112.567114
 | issue = 3
 | journal = [[Journal of the ACM]]
 | pages = 289–317
 | title = All pairs shortest paths using bridging sets and rectangular matrix multiplication
 | volume = 49| arxiv = cs/0008011| s2cid = 1065901 }}.</ref><ref>{{citation
 | last = Chan | first = Timothy M. | author-link = Timothy M. Chan
 | date = January 2010
 | doi = 10.1137/08071990x
 | issue = 5
 | journal = [[SIAM Journal on Computing]]
 | pages = 2075–2089
 | title = More algorithms for all-pairs shortest paths in weighted graphs
 | volume = 39| citeseerx = 10.1.1.153.6864 }}.</ref> In addition, because of the high constant factors in their running time, they would only provide a speedup over the Floyd–Warshall algorithm for very large graphs.