Shortest Paths: Dijkstra’s Algorithm

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

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