In this blog post we will have a look at Dijkstra’s shortest path algorithm. We will examine an example that illustrates the steps involved in the algorithm. The implementation will be posted in the next blog post as part 2.

Part 1 – Introduction to Dijkstra’s shortest path algorithm
Part 2a – Graph implementation in Python
Part 2b – Graph implementation in Java
Part 3a – Priority queue in Python
Part 3b – Priority queue in Java
Part 4a – Python implementation
Part 4b – Java implementation

Part 1 – Introduction to Dijkstra’s shortest path algorithm

Consider the graph below. You start at node ‘a’ and want to reach node ‘i’. Note that each edge has a weight (or cost) associated to it. For example, the cost to get from ‘a’ to ‘b’ is 0.95. As you can see there are many possible paths from ‘a’ to ‘i’, and we are interested in the shortest one.

An algorithm that lets us determine the shortest distance from ‘a’ to all other nodes was developed by Edsger W. Dijkstra. His algorithm works as follows.

Step 0 (initialization): We assign to all nodes a distance value. Since we start at ‘a’, the distance to ‘a’ is zero. All other nodes have a distance value of ‘inf’ which stands for infinity. At all times these distance values represent the distance to our source node ‘a’. We maintain a set S that contain all nodes that we can reach so far.

Step 1 (add new node with smallest distance): We add to S the node with the smallest distance. Since ‘a’ has a distance of zero and all other nodes have a distance of ‘inf’, we add ‘a’ to S.

Step 2 (update distances): Now, we can reach new nodes from ‘a’ by discovering the edges {a, b}, {a, d} and {a, e}. The distances to nodes ‘b’, ‘d’ and ‘e’ are updated, for instance the distance to ‘b’ is reduced from ‘inf’ to 0.95.

————————————————————————————–

Repeat step 1 (add new node with smallest distance): In the next step we consider all nodes that touch our set S via an edge. These are the nodes ‘b’, ‘d’ and ‘e’. Among these nodes we add the one to S that has the shortest distance to our source node ‘a’, and that is node ‘d’ with a distance of 0.72.

Repeat step 2 (udpate distances): After adding node ‘d’ we discover the new edges {d, e} and {d, g}. We repeat step 2 by updating the distances, i.e. possibly reducing the distances to ‘e’ and ‘g’.

————————————————————————————–

Now we repeat step 1, i.e. we consider all nodes that touch our set S via an edge. These are the nodes ‘b’, ‘e’ and ‘g’. Among these nodes we add the one to S that has the smallest distance value, and that is node ‘g’.

We repeat step 2 by updating the distances, i.e. we have just added node ‘g’ and consequently discovered edges the new edges {g, e} and {g, h}. We can possibly reduce the distance values for ‘e’ and ‘h’. In order to reconstruct the shortest path we do the following: If we update, i.e. reduce the distance of a node, we assign to it a ‘predecessor node’. For example, we reduce the distance of node ‘h’ because using edge {g, h} yields a smaller distance. This means we come from ‘g’ in order to reach ‘h’, so the predecessor of ‘h’ is ‘g’. Later this will allow us to reconstruct the shortest path from ‘a’ to ‘i’ by considering the predecessor of ‘i’, than following that predecessor and on so until we reach the source node ‘a’.

We can store the predecessors in a dictionary which initially looks like this:
{ ‘a’:’a’, ‘b’:none, ‘c’:none, ‘d’:none, ‘e’:none, ‘f’:none, ‘g’:none, ‘h’:none, ‘i’:none }

When we first applied step 2 we reduced the distance of nodes ‘b’ and ‘d’ due to the edges {a, b} and {a, d}. The dictionary is modified as follows:
{ ‘a’:’a’, ‘b’:’a’, ‘c’:none, ‘d’:’a’, ‘e’:none, ‘f’:none, ‘g’:none, ‘h’:none, ‘i’:none }

————————————————————————————–

Now we repeat step 1, i.e. we consider all nodes that touch our set S via an edge. These are the nodes ‘b’, ‘e’ and ‘h’. Among these nodes we add the one to S that has the smallest distance value, and that is node ‘b’.

We have added node ‘b’ to our set S. Now, what’s really important about this algorithm is that once we’ve added a node to S, it is guaranteed that the distance value of this node can’t be reduced any further, i.e. we have found its minimum distance. This is the heart of this shortest path algorithm. It was Dijkstra who proved this property and hence the algorithm is named after him.

Steps 1 and 2 are repeated until there are no nodes left that touch set S via an edge.

————————————————————————————–

Dijkstra’s shortest path algorithm summarized:

Step 0 (initialization): Assign to all nodes a distance value of ‘inf’, except for the source node which has a distance of zero. Initialize an empty set S. Initialize a predecessor dictionary.

Repeat loop:
____Step 1: add to S the node with the smallest distance (among the nodes that touch S via an edge). Call that node u.
____Step 2: for u consider all new outgoing edges {u, v1}, {u, v2}, …, {u, vk} (i.e. edges that lead to nodes which are not yet in S). Check if these edges lead to a smaller distance value for the nodes v1, v2, …, vk. If it does for vj, update the distance for vj to the smaller value and set the predecessor of vj to u.
____ If there are no nodes left that touch S via an edge, then break the loop.

Note: Dijkstra’s algorithm not only computes the shortest distance from the source node ‘a’ to our target node ‘i’, but it also computes the distance to all the other nodes as well.

————————————————————————————–

Exercise
a) Finish the task of finding the shortest distance from ‘a’ to ‘i’.
b) After having computed the shortest distance from ‘a’ to ‘i’ try to reconstruct the shortest path from ‘a’ to ‘i’ by using the predecessor dictionary.

Solution
Answer a) We continue with the steps in Dijkstra’s algorithm:

The shortest distance from ‘a’ to ‘i’ is therefore 1.41.

Answer b) We have computed the shortest distance from ‘a’ to ‘i’. In order to reconstruct the shortest path we need the predecessor dictionary which looks like this:
{‘a’: ‘a’,
‘b’: ‘a’,
‘c’: ‘e’,
‘d’: ‘a’,
‘e’: ‘d’,
‘f’: ‘e’,
‘g’: ‘d’,
‘h’: ‘e’,
‘i’: ‘h’}

We start from our target node ‘i’. Its predecessor is node ‘h’.
The predecessor of ‘h’ is ‘e’.
The predecessor of ‘e’ is ‘d’.
The predecessor of ‘d’ is ‘a’, which is our source node.
So starting at ‘i’ we get the sequence (i, h, e, d, a). If we reverse it we get the shortest path (a, d, e, h, i).