23 Dijkstra's Algorithm

Find the shortest path in a directed graph from a fixed vertex $s$.

Setting:

• A directed graph $G=(V,E)$ with $n$ vertices
• Edge-lengths given by length: $E\to {\mathbb{R}}^{\ge 0}$
• A fixed source vertex $s$$
• Question: For each $v\in V$, find length of shortest $s-\to v$ path.

Observe that we are asked to need to find $n-1$ ($n-1$ values because $s\to s$ is $0$) values

Algorithm

$$\begin{array}{rl}\text{Algorithm: }& \text{Finding shortest paths from }s\text{ to all other vertices in a directed graph }\\ & G=(V,E)\text{ and }\text{edge-lengths give by length }:E\to {\mathbb{R}}_{\ge 0}\end{array}$$ $$\begin{array}{rl}1.& \text{Let }S\text{ be set of explored vertices}\\ 2.& \text{For each }u\in S\text{ we store distance of shortest }u\to s\text{ path in }\mathrm{dist}(u)\\ 3.& \text{Initialize }S=\{s\},\text{ and }\mathrm{dist}(s)=0\\ 4.& \text{while }S\ne V\text{ do}\\ 5.& \text{Select }v\notin S\text{ which minimises }\mathrm{temp}\text{-}\mathrm{dist}(v)=\underset{\begin{array}{c}(u,v)\in E\\ u\in S\end{array}}{\min }(\mathrm{dist}(u)+\mathrm{length}(u,v))\\ 6.& \text{Add }v\text{ to }S\text{ and set }\mathrm{dist}(v)=\mathrm{temp}\text{-}\mathrm{dist}(v)\\ 7.& \text{end while}\end{array}$$

Running time is $O(mn)$ where $n,m$ is number of vertices and edges respectively.

• while loop runs $(n-1)$ time from $|s|=1$ to $|s|=n$
• within each while loop we need $O(m)$ time

Example of Dijkstra’s

Correctness of Dijkstra’s Algorithm

Correctness of each intermediate step

Theorem

Consider the set $S$ at any point during the algorithm. For each $u\in S$, the quantity $\mathrm{dist}(u)$ stores the value of shortest $s\to u$ path.

We prove this theorem by induction on $|S|$:

• Base case: $|S|=1$ and $\mathrm{dist}(s)=0$
• Inductive Hypothesis : Suppose that the theorem holds for $|S|=k$
• Suppose that we now grow $S$ by one more vertex by adding $v$.
• By line 5: $\mathrm{tmp}-\mathrm{dist}(v)=\mathrm{dist}(u)+\mathrm{length}(u,v)$ for some $u\in S$
• Suppose there is a $s\to v$ path $P$ shorter than $\mathrm{dist}(v)$
• Let this path $P$ leave $S$ via the edge $(x,y)$ for some $x\in S,y\notin S$

• Contradiction

Comments on Dijkstra’s algorithm

• Modify the algorithm to maintain the actual shortest paths from $s$
  • Not just the distance of shortest paths!
• Dijkstra’s algorithm is very similar to Breadth First Search (BFS)
• Can we apply this algorithm to undirected graphs ?
  • Yes! Just replace an undirected edge $u-v$ of length $l$ with two directed edges $u\to v$ and $v\to u$ of length $l$ each

Dijkstra’s algorithm fails if edge lengths can be negative!