What is Dijkstra's algorithmDijkstra is a fundamental algorithm for all link state routing protocols. It permits to calculate a shortest-path tree, that is all the shortest paths from a given source in a graph.
Edge cases for Dijkstra's algorithmDijkstra applies in following conditions:
- the link metrics must take positive values (a negative value would break the algorithm)
- but the links can be directional, no problem.
- if the graph contains unconnected parts, it does not work
So, if we take the example below, with a source node s and a target t, the algorithm will work and provide the shortest paths from s to all nodes (and thus to t).
Step by step example of Dijkstra's algorithm operations (pictures).You have to understand how Dijkstra algorithm works before we can actually implement it. There are two phases in Dijkstra's routing operations:
1- the initialisation of a predecessor structure that will keep for every node 'x' its father (that is the predecessor of 'x' in the shortest path from 's' to 'x') and the cost of the shortest path from 's' to 'x'.
2- the visiting of all nodes to update the predecessor structure
Let's see how the initialisation phase looks like on our example:
root of our shortest path tree. And the cost from 's' to 's' is... well, 0!
For all other nodes, we do not know the predecessor and we initiate the algorithm with an infinite cost for every node.
Now, the second phase where we apply a special treatment on all not yet visited nodes:
- Dijkstra always picks the non-visited node with the lowest cost in the predecessor structure. Here it's the root 's', as it has a cost 0 and all other an infinite cost.
- the neighbors of s are a and b.
- The cost of the path from s to a is: 0+2=2 < infinity, so we update the predecessor structure of a to 's',2
- The cost of the path from s to b is: 0+ 1=1 < infinity, so we update the predecessor structure of b to 's',1
- once we have handled all neighbors of 's', our work with 's' is done. We mark it as visited.
Then, we recurse Dijkstra's operations for the non-visited node with the lowest cost in the predecessor structure. Here it's the node 'b', as it has a cost 1 and all other non-visited nodes have a cost >=2.
In our case, the path s ---> a was better as 2 < 1+ 2; so, we do not update a's predecessor.
But the path s-->d had previously infinite cost > 1+2; so, we update d's predecessor data.
For the next recursion, the source is a
Source code for Dijkstra's algorithm in Python.
Let's go for the implementation of Dijkstra's routing algorithm with Python in my next post, now that we have understood the basic stages.
If you need to prepare interviews and revise the classical algorithms, have a look to "Cracking the Coding Interview: 150 Programming Questions and Solutions" by Gayle Laakmann McDowell. It's a great book, I am sure you are going to love it.