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