## Introduction

I have a startling admission to make. When I was a student, I scoffed at Dijkstra’s algorithm – I had paid it no mind and hoped that it wouldn’t come up in any exams I took. I was lucky and managed to avoid it all the way into adulthood, I was free and unscathed and proud of it.

Then it happened – some colleagues and I were considering a shortest path problem and one remarked “Ah! Dijkstra’s algorithm can be useful here”. Everyone else around me nodded in unison whereas I was looking around desperately hoping I’d find the shortest path out of this situation (see what I did there?).

Better late than ever, it’s time for me to get my head around Dijkstra’s algorithm and add a corner stone in my knowledge of algorithms that has been missing for a decade. If you’re new to Dijkstra’s algorithm or wanted a gentle reminder, this post is for you. If you have any criticisms of the drawings used in this blog post then I implore you to click here.

## Definitions

As always we begin with definitions. Let $G$ be a connected graph, $G = (V(G), E(G))$ where $V(G)$ is the set of all vertices in $G$ and $E(G)$ is the set of all edges in $G$.

Let $l(e)$ represent the length of an edge $e$, $e \in E(G)$. For every edge $e$ in $E(G)$, $e \in E(G)$, let $l(e) > 0$.

The l-length of a path $P$ is defined as

(1) $l(P) = \sum_{e \in E(P)} l(e)$

Given vertex $x$ and vertex $y$ in $V(G)$, an l-shortest $xy$ path is an $xy$-path $P$ that minimises $l(P)$.

Example 1:

There are many paths from vertex $x$ to vertex $y$, the path that minimises the l-length between $x$ and $y$ is the path illustrated by wiggly lines $\{x,b,c\}$. $l(P) = l(xb) + l(bc) + l(cy) = 1 + 1 + 1 = 3$.

## Dijkstra’s Algorithm

For vertices $x$ and $y$, Dijkstra’s algorithm finds a l-shortest path from vertex $x$ to vertex $y$. The algorithm maintains a tentative distance from $x$ – called $D(v)$ for each $v$ in $V(G)$, $\in V(G)$.

As the algorithm progresses, $D(v)$ will be updated. At each step of the algorithm, we finalise $D(u)$ for some vertex $u$. By the end of the algorithm, all $D$ values for each vertex $u \in U$ will be equal to the correct value

(2) $D(u)=l(P^{*}_u) = \sum_{e \in E(P^{*}_u)} l(e)$

for some l-shortest $xu$-path $P^{*}_{u}$.

In other words, $D(u)$ is the distance from vertex $x$ to vertex $u$. $P^{*}_{u}$ is the l-shortest path from vertex $x$ to vertex $u$. Dijkstra’s algorithm proceeds such that the final value of $D(u)$ will equal to $P^{*}_{u}$, $D(u) = l(P^{*}_{u})$

## Dijkstra’s Algorithm – Description

Begin by setting $U = V(G)$; $U$ is the set of vertices for which $D$ are not finalised.

Set $D(x) = 0$, where $x$ is the base node and $D(v) = \infty$, $\forall v \neq x$.

Repeat

If $U = \emptyset$ stop

There are no vertices with a not finalised $D$ value

Otherwise; select $u \in U$ with $D(u)$ minimal. Delete $u$ from $U$ (thereby finalising the D value of $u$). Hold deletions from $U$ in a set $C$.

For any vertex $v \in U$ where $v$ is adjacent to $u$ and it satisfies

$D(v) > D(u) + l(uv)$

replace $D(v)$ by $D(u) + l(uv)$.

If not, then keep $D(v)$ the same value. It might help to define $D_i(v)$ to be the value of $D(v)$ at iteration $i$ in the algorithm. We update $D(v)$ if $D_i(v) < D_{i-1}(v)$

Example 2: Consider a graph $G$

Run Dijkstra’s algorithm with base vertex $x$.

$i=1:$

$U = \{a,b,c,d,x\}$, $C = \emptyset$

$D_0(x) = 0$ and $D_0(a) = D_0(b) = D_0(c) = D_0(d) = D_0(c) = D_0(d) = \infty$

Select vertex with smallest $D$ value and remove it from $U$.

Here, vertex $x$ has the smallest $D$ value so we remove it from $U$ (and add it to $C$), thereby finalising it’s $D$ value.

For every vertex $v \in U$ adjacent to $x$, and satisfying $D(v) > D(x) + l(xv)$, replace $D(v)$ by $D(x) + l(xv)$.

Since the D values are all infinite initially, we can update all $D$ values:

$D_1(a) = D_0(x) + l(xa) = 0 + 1 = 1$

$D_1(b) = D_0(x) + l(xb) = 0 + 4 = 4$

$D_1(c) = D_0(x) + l(xc) = 0 + 1 = 1$

$D_1(d) = D_0(x) + l(xd) = 0 + 3 = 3$

$i=2:$

$U = \{a,b,c,d\}$, $C = \{x\}$

$D_1(a) = 1 , D_1(b) = 4, D_1(c) = 1, D_1(d) = 3$

Select vertex with smallest $D$ value and remove it from $U$.

Here, vertex $a$ and vertex $c$ have the smallest $D$ value so we arbitrarily remove $c$ from $U$ (and add it to $C$), thereby finalising it’s $D$ value.

For every vertex $v \in U$ adjacent to $c$, and satisfying $D(v) > D(c) + l(cv)$, replace $D(v)$ by $D(c) + l(cv)$.

All relevant $D$ values:

$D_2(d) = D(c) + l(cd) = 1 + 1 = 2$

$D_2(d) < D_1(d)$ so update $D(d)$. All other $D$ values remain the same.

$i=3:$

$U = \{a,b,d\}$, $C = \{x, c\}$

$D_2(a) = 1 , D_2(b) = 4, D_2(d) = 2$

Select vertex with smallest $D$ value and remove it from $U$.

Here, vertex $a$ has the smallest $D$ value so we remove $a$ from $U$ (and add it to $C$), thereby finalising it’s $D$ value.

For every vertex $v \in U$ adjacent to $a$, and satisfying $D(v) > D(a) + l(av)$, replace $D(v)$ by $D(a) + l(av)$

All relevant $D$ values:

$D_3(b) = D(a) + l(ad) = 1 + 5 = 6$

$D_3(b) > D_2(b)$ so don’t update $D(a)$. All other $D$ values remain the same

$i=4:$

$U = \{b,d\}$, $C = \{x, c, a\}$

$D_3(b) = 4, D_3(d) = 2$

Select vertex with smallest $D$ value and remove it from $U$.

Here, vertex $d$ has the smallest $D$ value so we remove $d$ from $U$ (and add it to $C$), thereby finalising it’s $D$ value.

For every vertex $v \in U$ adjacent to $d$, and satisfying $D(v) > D(d) + l(dv)$, replace $D(v)$ by $D(d) + l(dv)$

All relevant $D$ values:

$D_4(b) = D(d) + l(db) = 2 + 1 = 3$

$D_4(b) < D_3(b)$ so update $D(b)$. All other $D$ values remain the same

$i=5:$

$U = \{b\}$, $C = \{x, c, a, d\}$

$D_4(b) = 3$

Select vertex with smallest $D$ value and remove it from $U$.

Here, vertex $b$ has the smallest $D$ value so we remove $b$ from $U$ (and add it to $C$), thereby finalising it’s $D$ value.

For every vertex $v \in U$ adjacent to $b$, and satisfying $D(v) > D(b) + l(bv)$, replace $D(v)$ by $D(b) + l(bv)$

There are no adjacent vertices to $b$ in $U$. So do not replace $D(b)$.

Since $U = \emptyset$, we stop. Our final $D$ values are:

$D(a) = 1, D(b) = 3, D(c) = 1, D(d) = 2, D(x) = 0$

$D(i)$ represents the l-length of the shortest path from vertex $x$ to vertex $i$ for $i \in \{a, b, c, d\} = V(G) \setminus U = C$

## Shortest Path Rooted Trees

We can use Dijkstra’s algorithm to construct a spanning tree $T$ such that for any vertex $y \in V(G)$, the unique $xy$-path in $T$ is an l-shortest $xy$-path. Such a spanning tree $T$ is called an l-shortest paths tree rooted at $x$.

Building T

For any vertex $v$ which is not the base vertex, $v \neq x$, the parent of $v$ is the last vertex $u$ such that we replaced $D(v)$ by $D(u) + l(uv)$ during the running of Dijkstra’s algorithm.

In other words, what was the vertex we considered which caused us to update the value of $v$ – this is the parent vertex of $v$. If $D(v)$ was replaced at step $i$, which vertex did we delete from $U$?

$T$ is obtained by drawing an edge from each vertex $v \neq x$ to its parent.

Example 3: If we look at the running of Dijkstra’s algorithm running in the previous example, we can look at the vertices and discover its parent vertex.

$T = \{ (x,a), (x,c), (c,d), (d,b) \}$

T is the shortest path tree rooted at $x$

Before we learn how $T$ is the l-shortest path tree rooted at $x$, we consider a lemma.

Lemma 1: $T$ is a tree and for each $u \in V(G)$ we have $D(u) = l(P_u)$ where $P_u$ is the unique $xu$-path in $T$.

Proof:

Setup

After any step $i$, we have a set $C = V(G) \setminus U$. $C$ contains vertices whose $D$ value is finalised – for these vertices we know their parents.

Let $T_C$ be obtained by drawing an edge from $v \in C \setminus \{x\}$ to its parent vertex. So $V(T_C) = C$ ($x$ is included but doesn’t have an edge to a parent vertex because it’s a base vertex and has no parent).

At every stage $i$, we’re growing $C$ and $T_C$.

Induction

We want to show by induction on $|C|$ that $T_C$ is a tree and for each $u \in V(T_C)$ we have $D(u) = l(P_u)$ where $P_u$ is the unique $xu$-path in $T_C$.

Consider the following

Base step: Start with $V(T_C) = \{x\}$ and no edges, which is a tree, with $D(x) = 0 = l(P_x)$

Induction step: Suppose we are at stage $i$ in the algorithm and we want to finalise the $D$ value of some vertex $u \in U$. When we do this, we remove $u$ from $U$, add $u$ to $C$ and add an edge from $u$ to its parent. This is the same as adding a terminal vertex (leaf) to $T_C$ and adding a terminal vertex to $T_C$ gives us another tree (the tree definition is not violated). Let $v$ be a parent vertex for the vertex $u$ under consideration. If $v$ is a parent for $u$, then by definition we have

$D(u) = D(v) + l(vu)$

we also know that $D(v) = l(P_v)$, $v \in V(G)$

$D(u) = l(P_v) + l(uv) = \sum_{e \in E(P_v)} l(e) + l(uv) = l(P_u)$

hence we prove

$D(u) = l(P_u)$

Theorem 1: $T$ is an l-shortest paths tree rooted at $x$.

Proof:

Setup

For each $u \in V(G)$, let $D^*(u) = l(P^*_u)$ for some l-shortest $xu$-path, $P^*_u$.

This is the actual shortest path from vertex $x$ to vertex $u$.

We want to show that in each step of the algorithm, when $u$ is deleted from $U$ we have

$D(u) = D^*(u)$

We do this using a proof by induction and contradiction.

Base case

Consider the step where we delete $u$ from $U$ (we finalise the $D$ value for $u$). Suppose that

(*) $D(u) > D^*(u)$

(*) is our contradiction hypothesis, we want to show that (*) cannot be true so let’s see what it implies.

Let $C = V(G) \setminus U$. We know from Lemma 1 that for every vertex $v$ in $T_C$

$D^*(v) = D(v)$ (vertex $v$ has the shortest path distance from base vertex $x$)

Let $(y,y^{})$ be the first edge of $P^*(u)$=\$ (l-shortest $xu$-path) where $y \notin U = y \in C$ ($y$ has its $D$ value finalised) and $y^{} \in U$.

Since $y \in C$, its $D$ value is finalised and it is part of $T_C$, so we know

$D(y) = D^*(y)$

Now consider $y^{}$, before we finalise the $D$ value if $y^{}$ (remove $y^{}$ from $U$) we have to be sure that $D(y) + l(yy^{})$ has to be smaller than or equal to $D(y^{})$. This is by the rules of Dijkstra’s algorithm, we don’t add it if it doesn’t satisfy this rule. We finalise $D(y^{})$ when it cannot get any smaller.

$D(y^{}) \leq D(y) + l(yy^{})$

$D(y^{}) \leq D^*(y) + l(yy^{})$ (since $y^{} \in C$)

$D(y^{}) \leq l(P^*_y) + l(yy^{})$ (by identity (2))

If $P^{*}_{u}$ is the shortest path from $x$ to $u$ then any subpath of $P^*_u$ would also be the shortest path. $l(P^*_y) + l(yy^{})$ is a subpath of $P*_u$ so

$D(y^{}) \leq l(P^*_y) + l(yy^{}) \leq l(P^*_u)$

$D(y^{}) \leq l(P^*y) + l(yy^{}) \leq D^*(u)$

Putting this together, we have the shortest path

$D(y^{}) \leq D^*(u)$

since our contradiction hypothesis supposes $D(u) > D^*(u)$

$D(y^{}) < D(u)$

but this is a contradiction. Dijkstra’s algorithm finalises the $D$ value for a vertex in $U$ with the smallest possible $D$.

In this case we are supposing that vertex $u$ is being finalised (has smallest $D$ value). But Dijkstra’s algorithm should not have selected $u$ because we have just shown that there is another vertex in $U$ with a smaller $D$ value – namely vertex $y^{}$. The $D$ value of $y^{}$ is strictly less than the $D$ value of $u$. So for $u$ to have its $D$ value finalised, it must have the lowest $D$ value for all vertices $u \in U$ which includes $y^{`}$. Hence

$D(u) = D^*(u)$

This shows that our contradiction hypothesis (*) cannot be true. At every stage, we add a vertex $u$ to $C$ (and to $T$) which has the smallest distance from the vertex $x$ to $u$. Therefore $T$ is an l-shortest path tree from vertex $x$ to vertex $u$.

There we have it, we’re done with our shortest path through Dijkstra’s algorithm.

## References

1. I’m indebted to Marc Lackenby’s treatment of the subject. In many ways, this is a poor man’s explanation of this video: https://www.youtube.com/watch?v=Q9vckauJW_0