Dijkstra’s Shortest Path Algorithm

• A Greedy Algorithms to find the shortest path
• Takes in a single source, finds the shortest path to all other vertices

Constraints

• Single source: Path to all vertices
• Directed or Undirected graphs
• No negative weights allowed
• No negative weight cycles allowed

Algorithm

• Maintain a set of explored nodes $S$ for which algorithm has determined $d[u]=$ length of a shortest $s⇝u$ path
  • Initialize $S\leftarrow \{s\}$ and $d[s]\leftarrow 0$, $d[\text{not }s]\leftarrow \infty$
  • Repeatedly
    • Choose unexplored node $v\notin S$ which minimizes: $\pi (v)=\underset{e=(w,v):w\in S}{\min }d[w]+{\ell }_e$
      • This is the shortest total path formed by adding a node that neighbors $S$ to an existing path in $S$
    • Add $v$ to $S$
    • Set
      • $d[v]\leftarrow \pi (v)$
      • $pred[v]\leftarrow$ edge taken to get from chosen $w$ in $\pi$ to $v$

Proof

Invariant: For each node $u\in S:d[u]=$ length of a shortest $s⇝u$ path. Proof by induction on $|S|$ Base case: $|S|=1$ is easy since $S=\{s\}$ and $d[s]=0$ Inductive Hypothesis: Assume true when $|S|=k$ for $k\ge 1$ Inductive Step: $|S|=k+1$

• Let $V$ be the next node added to $S$, and let $(u,v)$ be the final edge
• A shortest $s⇝u$ path plus $(u,v)$ is an $s⇝v$ path of length $\pi (v)$
• Consider any other $s⇝v$ path $P$. We show that it is no shorter than $\pi (v)$
• Let $e=(x,y)$ be the first edge in $P$ that leaves $S$, and let $P^{\prime }$ be the subpath from $s$ to $x$.
• The length of $P$ is already $\ge \pi (v)$ as soon as it reaches $y$:
  • $\ell (P)$
  • $\ge \ell (P^{\prime })+{\ell }_e$ (non-negative lengths)
  • $\ge d[x]+{\ell }_e$ (inductive hypothesis)
  • $\ge \pi (y)$ (definition of $\pi$)
  • $\ge \pi (v)$ (Dijkstra chose $v$ instead of $y$)

Implementation

Critical optimizations:

• For each unexplored node, explicitly maintain a $\pi [v]$ instead of computing every time
• Use a min-oriented Priority Queue to maintain which $v$ to choose

Pseudocode:

dijkstras
	PriorityQueue pq
	pq.add(source, 0)
	for v in other verticies
		pq.add(v, infinity)
	while pq is not empty
		p = pq.removeSmallest()
		for edge from p
			relax edge
	
relax edge from v to u with weight w
	if d[u] + w < d[v]
		d[v] = d[u] + w
		p[v] = u
		pq.changePriority(v, d[v])

Time Complexity

• $O(V\log V+V\log V+E\log V)\sim O(E\log V)$ time complexity if using Priority Queue
• $O(V^2)$ without heap