Input: Graph G, vertices S (start), T (terminate) Declare: H (initially empty heap) 1: For all vertices v 2: if v == S then v.cost := 0 3: else v.cost := infinity 3: Insert v into H 4: Repeat 5: M := ExtractMin(H) 6: For each vertex A attached to M 7: w := cost of edge from M to A 8: if (M.cost + w < A.cost) 9: DecreaseKey(A,M.cost + w) 10: A.backlink := M 11: Until M = T 12: Output T.cost 13: Output vertices on chain of backlinks from T to S
Dijkstra’s algorithm sets the cost of each vertex (except the starting vertex) to infinity and puts all the vertices onto a heap. You then extract the cheapest vertex from the heap — call it M — and examine each vertex A adjacent to M. If the cost of M plus the cost of the edge joining M to A is cheaper than the current cost of A (that is, if there’s a cheap path to A through M), you create a link from A to M and decrease A’s key to represent the new cost. You continue extracting successive nodes until you reach T, the target vertex. The value of T is the cost of the shortest path. The links from T back to the starting vertex indicate the shortest path.
As you can see in Figure 1, the DecreaseKey() on line 9 is the most time-consuming operation of the inner loop. Since Dijkstra’s algorithm is important in network routing and other applications, it would be nice to find a heap implementation that makes this operation as fast as possible. This is the primary motivation for the Fibonacci heap.
—- By John Boyer
Running Time: (http://en.wikipedia.org/wiki/Dijkstra’s_algorithm)
The simplest implementation of the Dijkstra’s algorithm stores vertices of set Q in an ordinary linked list or array, and operation Extract-Min(Q) is simply a linear search through all vertices in Q. In this case, the running time is O(V^2).
For sparse graphs, that is, graphs with much less than V^2 edges, Dijkstra’s algorithm can be implemented more efficiently by storing the graph in form of adjaceny lists and using a binary heap or Fibonacci heap as a priority queue to implement the Extract-Min function. With a binary heap, the algorithm requires O((E+V)logV) time, and the Fibonacci heap improves this to O(E+VlogV).