## 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.

Vertex | Parent | Edge | Edge length |

a | x | (x,a) | 1 |

b | d | (d,b) | 1 |

c | x | (x,c) | 1 |

d | c | (c,d) | 1 |

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

- 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

## Leave a Reply