Content deleted Content added
Freshman404 (talk | contribs) |
Undid revision 710367686 by Freshman404 (talk) per WP:SEEALSO — already prominently linked in main text of article |
||
Line 44:
==Analysis==
The [[time complexity]] of this algorithm, using [[Fibonacci heap]]s in the implementation of Dijkstra's algorithm, is {{math|O(''V''<sup>2</sup>log ''V'' + ''VE'')}}: the algorithm uses {{math|O(''VE'')}} time for the Bellman–Ford stage of the algorithm, and {{math|O(''V'' log ''V'' + ''E'')}} for each of {{math|''V''}} instantiations of Dijkstra's algorithm. Thus, when the graph is sparse, the total time can be faster than the [[Floyd–Warshall algorithm]], which solves the same problem in time {{math|O(''V''<sup>3</sup>)}}.<ref name="clrs"/>
==References==
| |||