What is the Dijkstra Algorithm?
- Perform Dijkstra's algorithm starting from node A.
- Draw the shortest-path tree for the result.
- Watch the path to node K. Walk along the nodes and perform
the algorithm for each node.
- Is the routing information along the path consistent (i.e.
each node will use the same link as originally calculated starting from node
A)?
Look at the following topology:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgj02I2Foihj4d7U9DV2FWjxmpbonoZ0q_4oEZhB_4Ya7H9pisNQXP46khLSdla7GihcxBrbvzMMbp07Q_6pvko0cAnePPWc6VIxGTDu2V8ixQbiFY_s7o1pnsrR0kYM6MBjzegPKDuh5Q/s1600/Dijsktra+-+Beispiel.png) |
Example of a topology |
Now at first step, create a table with all members of the "network" and write in these three factors:
Node, Parent & Distance.
From node A the parent is nothing = { }. Also the distance = 0.
Then go to the nodes next to A, node B:
The parent of node B is A, and the distance from B to A is 3.
Now to the next node -> node E, ... and so on.
Do this recursiv, if one parent has a lower distance, write the parent node with the lower distance in the table, instead of the one with the higher distance.
In the end, the table looks like this:
Through this table you can get the shortest path, which you can see in the following picture:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhNuit67lcT4eDxySuj9-AClQHeQJXhDKwlLfAi97J1aJAmbEHZi25VCgfPruJAqQTwwWtBzHju2nsDTG_hPl8j_fOMepGW3Gz4l76aMTA_FoEyC4gKVzY6crRukmWPLyK0XaBj87E4D1A/s400/Dijsktra+-+ftg.png) |
Shortest Path = 11 |