3 2. 2 1 3 . 1 LO
Dijkstra’s
Let
- D(v): cost of the least-cost path from the source node to destination ?v as of this iteration of the algorithm.
- p(v): previous node (neighbor of v) along the current least-cost path from the source to v.
- N′: a subset of nodes; v is in N′ if the least-cost path from the source to ?v is definitely known.
The centralized routing algorithm consists of an initialization step followed by a loop. The number of times the loop is executed is equal to the number of nodes in the network. Upon termination, the algorithm will have calculated the shortest paths from the source node ?u to every other node in the network.
Algorithm: (in the picture below)
Example: Given the following graph, the shortest paths of to node v,w,x,y, and z from node u in the view point of node u are computed as follows: (in the 2nd picture)
1. Initialization: the currently known least-cost paths from u to its directly attached neighbors.
2. Step 1: we look among those nodes not yet added to the set N′ and find that node with the least cost as of the end of the previous iteration. That node is x, with a cost of 1, and thus x is added to the set N′. Then we determine how to reach every node via x and see if we can improve the cost (get lower cost). The cost from u to v is unchanged (going to v via x has higher cost compare to go from u to v directly). The cost from u to w is updated because ?u can reach w via x has lower cost than going from u to w directly.
3. Step 2 : nodes v and ?y are found to have the least-cost paths (value 2). Then we add y to the set N′so that N′ now contains u,x and y. The cost to the remaining nodes not yet in N′, that is, nodes v,w and z, are updated
4. And so on for step 3, 4, 5, until no path to node can be updated or run out of nodes in ?N.
Task: implement Dijkstra’s algorithm and display this table for any node in this graph.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
