For marketers
who love technology
Home » , » Dijkstra routing algorithm: How it calculates a shortest path tree (step-by-step example with images)

Dijkstra routing algorithm: How it calculates a shortest path tree (step-by-step example with images)

What is Dijkstra's algorithm 

Dijkstra 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 algorithm 

Dijkstra 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:
As described in the above picture, the predecessor of the node 's' does not exist: s is the 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.

We visit all neighbors of 'b' and do the exact same operations as before to update their predecessor structure if b is a better father (meaning that the shortest path through b is better than the previously identified path).

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
 then d
then c
and finally t, but this step does not change any predecessor structure, so I do not have a picture for it.


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.

  

SHARE

About Gilles

0 comments :

Post a Comment