Dijkstra's Algorithm

Algorithm

Input	Graph (G).
Output	Sorted path from source to destination .
Complexity	O(vlogv+E).

Initialize (G, s)
   1 for each vertex v in V[G]
   2 do d[v]= ∞
   3 parent[v] =NIL
  4 d[s] =0


Relax (u, v, w)
    1 if d[v] > d[u] + w (u, v)
   2     then d[v] = d[u] + w (u, v)
   3                parent[v] ← u

DIJKSTRA (G, w, s)
1 Initialize (G, s)
2 S =Null
3 Q =V[G]
4 while Q ≠ Null
5 do u =EXTRACT-MIN(Q)
6     S =S union {u}
7 for each vertex v in Adj[u]
8       do RELAX(u, v, w).

Algorithm Description

Line 1 performs the usual initialization of d and parent values, and line 2 initializes the set S to the empty set. The algorithm Maintains the invariant that Q = V – S at the start of each iteration of the while loop of lines 4-8. Line 3 initializes the min-priority queue Q to contain all the vertices in V ; since S = NULL at that time, the invariant is true after line 3. Each time through the while loop of lines 4-8, a vertex u is extracted from Q = V – S and added to set S, thereby maintaining the invariant. (The first time through this loop, u = s.) Vertex u, therefore, has the smallest shortest-path estimate of any vertex in V – S. Then, lines 7-8 relax each edge (u, v) leaving u, thus updating the estimate d[v] and the predecessor parent[v] if the shortest path to v can be improved by going through u. Observe that vertices are Never inserted into Q after line 3 and that each vertex is Extracted from Q and added to S exactly once, so that the while loop of lines 4-8 iterates exactly |V| times.

C Code