Dijkstra's Shortest Path Algorithm

Main idea

Maintain the shortest path tree and grow it bit by bit.

Pseudo code

Given a set of all the vertices $V$, connecting edges $E$, distance map $\mathit{dist}: V * V \to \text{int}$, starting vertex $s$, and terminal vertex $t$, do the following.

1. Initialize the following variables:
   1. a shortest path tree set $\mathit{SptSet} = \emptyset$.
   2. a distance dictionary, which holds distances from the source vertex:
   $$
    \forall v \in V\backslash\{s\}. \mathit{Dist}[v] = \infty \\\\
    \mathit{Dist}[s] = 0
   .$$
2. While $\mathit{SptSet} \ne V$:
   1. Pick $u \in V\backslash\mathit{SptSet}$ s.t. $\forall v \in V\backslash\mathit{SptSet}. \mathit{Dist}[u] \le \mathit{Dist}[v]$
   2. $\mathit{SptSet} = \mathit{SptSet}\cup\{u\}$
   # Update the $\mathit{Dist}$ as follows.
   3. $\mathit{Adjacents} = E[u] \backslash \mathit{SptSet}$
   4. $for \mathit{adj} \in \mathit{Adjacents}:$
    1. $\text{if } \mathit{Dist}[u] + \mathit{dist}(u, adj) \le \mathit{Dist}[adj]:$
     1. $\mathit{Dist}[adj] = \mathit{Dist}[u] + \mathit{dist}(u, adj)$
3. Return $\mathit{Dist}[t]$.

Python 3 Code