Dijkstra's Shortest Path Algorithm

What is the Dijkstra Algorithm?

• http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
• http://de.wikipedia.org/wiki/K%C3%BCrzester_Pfad

• 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:

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:

Shortest Path = 11