# Implementing Dijkstra using (Fibonacci) Heap

Dijkstra Alogrithm:

```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)
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).

## 6 thoughts on “Implementing Dijkstra using (Fibonacci) Heap”

1. Sophie

Isn\’t it the notes from Algorithm Class?!

2. Feng

不是吧，我今天没去上课的说…

3. Sophie

ft, Lloyd听到伤心死，图论N周前就讲了，Shortest Path之Single Source… 我还以为是你复习的心得呢…

4. Feng

还没开始复习呢。这是做photography的homework时用到的…

5. 76Rex

Hello blogger, i must say you have high quality articles here.
Your page can go viral. You need initial traffic boost only.
How to get it? Search for; Mertiso’s tips go viral

6. Stacie Lavin

Hello!

You Need Leads, Sales, Conversions, Traffic for fengl.org ? Will Findet…

I WILL SEND 5 MILLION MESSAGES VIA WEBSITE CONTACT FORM

Don’t believe me? Since you’re reading this message then you’re living proof that contact form advertising works!
We can send your ad to people via their Website Contact Form.