Dijkstra's algorithm
The time complexity of this algorithm, using Fibonacci heaps in the implementation of Dijkstra's algorithm, is formula_5: the algorithm uses formula_6 time for the Bellman–Ford stage of the algorithm, and formula_7 for each of the formula_8 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 formula_9.