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

### Like this:

Like Loading...

*Related*

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

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

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

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

76RexHello 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