Shortest Path – Dijkstra’s Algorithm

We’ve all used those horrible SATNAV’s to get from one place to another. But how do they calculate the path we must follow in order to minimize the time needed.

This is a shortest distance problem, which shall be covered in this post via Dijkstra’s Algorithm.

Greedy

Even though it may not seem like it, Dijkstra’s algorithm is actually a greedy method for solving single-source shortest path problems.

The idea behind the greedy method is to perform a weighted BFS on a given graph, starting at some node n.

Dijkstra’s is commonly implemented with a heap priority queue, so that in each iteration; when we require to get the next node that we need to visit, then this chosen node will be the next closest to node n.

 

Dijkstra’s Example

Below is a simple little graph. Here we see the Alliance capitals, and there [made-up!] distances between each one.

Here, the number’s on the edges are the edges weights – or the distances between the nodes. The red boxes are the current shortest distances that the node can be reached in if we started from the node Stormwind. a * indicates infinity.

 

 

Now let’s say we’re currently residing in the node Stormwind, and we wish to travel to the node Exodar. What is the shortest distance that this can be done in? Well, let’s use Dijkstra’s to find out!

[i’ll use a few images, but not a lot]

Firstly, we need to make sure that we have implemented a priority queue – a good heap should serve us well :)
Now that we have this, our first task is to visit the node Stormwind, and then we look at all the node’s in Stormwind’s outlist – Ironforge – and ask ourselves, is 7 < infinity? The simple answer is ‘yes’, so we change Ironforge’s current shortest distance to 7:

Now that we have done this. We need to add all of the unvisited nodes in Stormwind’s outlist to the heap.

Now, remembering that at the root of a heap is always the minimum node, what we next need to do is chose the next node to visit. This next node should be the node that has the closest distance to the origin (Stormwind). Since Ironforge is the only node in the heap, then we just remove that node and traverse to it :)

Now, looking at the outlist of Ironforge, we see we have 3 nodes – Gnomergan, Darnassus and Stormwind again. Do you remember what the first thing we need to do is? Yep! We need to check the distances at each of the node’s to see if we have a new shortest distance.

Now, Gnomergan and Darnassus both have infinites, so they’re are blatantly obvious. But Stormwind does have a value! However, i am afraid that 7 is not less than 0. So we chance our distances with Gnomergan and Darnassus. The values that must be placed into them are the values 9 and 17 -  can you see why?

If you guessed 7+2 and 7+10, then you were correct, give yourself a pat on the back! :D

Next we have to add Gnomergan and Darnassus to the heap, we don’t add Stormwind as this node has already been visited. Since Gnomergan has the smallest distance, then this is our next node to visit.

Since now most of this should be obvious, then you should be able to see that the only node affected by visiting Gnomergan is Exodar, giving it the distance of 9+5=14, and then we add the Exodar to the heap (bubbling-up, remember, Darnassus is still in the heap!)

 

Now the next node we need to visit is Exodar, since this will be the root node of the heap as 14 < 17.

Unfortunately, all nodes from Exodar have all ready been visited, so we can’t add Darnassus to the heap – again! Also, 20 (14+6) is not less than 17, so we can’t update any distances either. Since this is the case, we then jump to the next ad final node – Darnassus; as it’s the only node left in the heap.

Looking at Darnassus, we see that 23 (17+6) is not less than Exodar’s current shortest distance of 14. So that means we terminate the algorithm and we are left with all the shortest distances to all the nodes from the one node Stormwind.

Answering the question, we see that the shortest distance to get from Stormwind to Exodar is 14, and if we implemented a tracker to keep record of the node’s we need to pass through, then we would see that we need to go through:

• Stormwind –> Ironforge –> Gnomergan –> Exodar

 

Complexity

Remembering that n represents the number of nodes and m represents the numbers of edges.

Since we implemented our priority queue as a heap, then the time complexity to remove the minimum element from the heap, as well as add new elements to the heap is O(log n). Now we need to take into consideration the fact of when we update the shortest distances of nodes, or the edge relaxation phase which takes O(deg(v)) which is O(n+m)

With this, the time Dijkstra’s spends at each node is O(m log n), whereas if we needed to visit all nodes, then the time complexity for a Dijkstra’s algorithm would be
O((n+m) log n)

So far, we have considered Dijkstra’s as a single source all targets, but what if we wanted an all sources all targets? Well the complexity would be O(n(n+m) log n)

Also, if we have a strongly (completely) connected graph. That is, a graph with n^2 edges, then the complexity of Dijkstra would be O(n^2 log n)

 

On a side note. If we decided to implement the priority queue as a simple linear search rather than a heap, then the time complexity of removing an element would be O(n), with the edge relaxation still being O(n+m), therefore the actual time complexity would be O(n^2 + m), which is worse than if we used a heap.