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

6 thoughts on “Implementing Dijkstra using (Fibonacci) Heap

  1. Sophie

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

    Reply
  2. 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

    Reply
  3. 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.

    IF YOU ARE INTERESTED, Contact us => lisaf2zw526@gmail.com

    Regards,
    Lavin

    Reply

Leave a Reply to Feng Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s