Algorithms

Dijkstra's original algorithm does not use a min-priority queue and runs in time O(|V|^2) (where |V| is the number of nodes). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E|+|V|\log|V|) (where |E| is the number of edges) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.

1  function Dijkstra(Graph, source):
2      dist[source] ← 0             // Initialization
3
4      create vertex set Q
5
6      for each vertex v in Graph:           
7          if v ≠ source
8              dist[v] ← INFINITY // Unknown distance from source to v
9              prev[v] ← UNDEFINED    // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14      while Q is not empty:          // The main loop
15         u ← Q.extract_min() // Remove and return best vertex
16         for each neighbor v of u: // only v that is still in Q
17             alt = dist[u] + length(u, v) 
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist[], prev[]

O(|V|^2)

O(|E|+|V|log|V|)

  int h = 1;<br />
  while(h <= nElems/3)
     h = h*3 + 1;               

  while(h>0)<br />
     {

     for(outer=h; outer<nElems; outer++)
        {
        temp = theArray[outer];
        inner = outer;

        while(inner > h-1 && theArray[inner-h] >=  temp)
           {
           theArray[inner] = theArray[inner-h];
           inner -= h;
           }
        theArray[inner] = temp;
        }  // end for
     h = (h-1) / 3;<br />
     }  // end while(h>0)

  }  // end shellSort()