Dijkstra's Shortest Path Algorithm

Grow the shortest path tree one by one.

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