About Dijkstra's Algorithm to find the Single source shortest paths

Pseudo-Code:

      DIJKSTRA$(G,s,w)$

1. INITIALIZE-SINGLE-SOURCE$(G,s)$
2. $S = \phi$
3. $Q = G.V$
4. while  $Q \neq \phi$
5.       $u = $EXTRACT-MIN$(Q)$
6.       $S = S \cup {u}$
7.       for vertex $v \in G.adj[u]$
8.             RELAX$(u,v,w)$

Explanation:

Here, $S$ is a set, which keeps track of the vertices whose final shortest weight path from the source vertex $s$ has been determined. $Q = G.V-S$. In the while loop, we extract the vertex from the priority queue $Q$, which has the minimum estimated distance from the source vertex $s$. Then this vertex $u$ is added to $S$, and all the edges connected to it are RELAXed. 

Dijkstra's algorithm is a greedy algorithm, as it always takes the vertex, not in $S$, which has the minimum distance from the source vertex $s$. 

Why does it work?

Basically, we try to prove that the following loop invariant is correct:

At the start of each iteration of the while loop in line-4, all the vertices in $S$ have their final shortest weight path determined. That is for all $v \in S, v.d = \delta(s,v)$.

Now, 

Initialization: Trivial. Since, $S = \phi$ initially.

Maintenance: See the figure given above (taken directly from CLRS). Here $s$ is the source vertex, $x$ is in $S$, that is the last vertex in $S$ that is in the path from $s$ to $u$. And, $y$ is the first vertex in the path that is not int $S$. 

Now, assume that $u.d \neq \delta(s,u)$, that is, $u.d$ is not equal to the minimum path weight, even after $u$ is added to $S$. Therefore, we try to get a contradiction here.

Now, when $x$ was added to $S$, then $x.d = \delta(s,x)$, and using the convergence property (which is stated below), we can say that $y.d = \delta(s,y)$.

Convergence Property:

If $s \to...\to u \to v$ is a shortest path in $G$ for some $u,v \in V$, and if $u.d = \delta(s,u)$ at any time prior to relaxing edge $(u,v)$, then $v.d = \delta(s,v)$ at all times afterwards.

Now, note that $y$ will be extracted after $u$. Because of that, at the time of extraction of $u$, $u.d \leq y.d$. Now since we have non-negative weights, thus $$\delta(s,y) \leq \delta(s,u)$$. And we know that $$y.d = \delta(s,y) \\ \leq \delta(s,u) \\ \leq u.d$$
The last step was taken due to the upper-bound property:

We always have $v.d \geq \delta(s,v)$ for all vertices $v \in V$, and once$v.d$ achieves the value $\delta(s,v)$, it never changes.

But since $y$ is extracted later than $u$, therefore $u.d \leq y.d$, but we've $u.d \geq y.d$ according the analysis above. So, because of that, we can say that $u.d = y.d$. So $y.d = \delta(s,y) = \delta(s,u) = u.d$, as all the inequalities change to equalities, since the first and last elements of the inequalities are equal. This would mean that $u.d = \delta(s,u)$, which is a contradiction.

Thus the loop invariant exists here too.

Termination: Easy. As the maintenance makes sure that every vertex inside $S$ has the right path weight (and parent), therefore in the end, when $Q = \phi$ and $S = G.V$, we'll have the loop invariant satisfied.

Therefore, we can say that Dijkstra's algorithm works correctly. Cool!

Running time:

Note that we extract one vertex only once, and we have a total of $|V|$ vertices inside $Q$. Therefore, the outer while loop works $|V|$ times. And since one vertex is extracted only once, therefore, it's adjacency list is traversed only once, leading to the fact that the total number of time the inner  for loop works $|E|$ times. (Since there are a total of $|E|$ edges in total, obviously)

There are three priority queue operations here, INSERT( line 3), DECREASE-KEY (implicit in RELAX) and EXTRACT-MIN.
Therefore we can say that the total running time of the algorithm is: $$ O(|V|\times\text{(INSERT)}+|V|\times\text{(EXTRACT-MIN)}+|E|\times\text{DECREASE-KEY})$$

There are three possible implementations of the priority queue :

1. Array implementation: If we have every vertex numbered from 1 to $|V|$, then we can implement $Q$ using an array of length $|V|$. Then INSERT and DECREASE-KEY can be done in $O(1)$ time, and EXTRACT-MIN in $O(|V|)$ time. Therefore, a total of $O(|V|+|V|^2+|E|) = O(|V|^2)$ time is taken.
2. Min-heap implementation: Here BUILD-HEAP will take a total of $O(|V|)$ time, DECREASE-KEY and EXTRACT-KEY both will take $O(lg\text{ }|V|)$ time. Therefore, we have a total running time of $O((|E|+|V|)lg \text{ }|V|) = O(|E|lg\text{ }|V|)$ time.
3. Fibonacci Heaps: Here, the DECREASE-KEY can be implemented in $O(1)$  time. Thus a total running time of $O(|E|+|V|lg |V|)$.