2. Dijkstra\'s Link State Algorithm (for computing least cost paths) Consider th

Question

2. Dijkstra's Link State Algorithm (for computing least cost paths) Consider the 6-node network shown below, with the given link costs. 5 5 8 3 8 7 5 3 Before doing this problem, you might want to reread the section on Dijkstra's algorithm in chapter 5 and view this youtube video that fits our slides https://www.youtube.com/watch?v-V5-sqVTB49g. A. Using Dijkstra's algorithm, find the least cost path from source node u to all other destinations Show your work in tabular format, as in lecture slide for Chapter 5 (pg 5-15). N' D (u),p (u) D(v),p(v) D(w),p(w) D(x),p(x) D(y),p (y) D(z) ,p (z) Thus, the links in the least cost routing tree from node u to all destinations are? (ex. u-b, u-d, etc.) B.

Explanation / Answer

According to the video, the steps to follow to run dijkstra's algorithm is:

1.) Calculate which all links are directly connected to the source node. Write the distances for them in the table and the distance for the nodes not directly connected is considered infinity.

2.) We follow an iterative method, thus to proceed to next iteration, we find the minimum distance from the previous iteration and copy the node corresponding to the iteration in the set N'.(The set N' initially contains the source node). After this we find the distances of all the nodes from this node which we copied. We follow almost the same procedure, for links not directly linked we assume the distance to be infinity, but for links directly connected we follow a formula which says:

Distance = min(D(v), D(w)+C(v,w))

Here the function D() evaluates to the distance between the initial source node and the node in argument.And the function C() evaluates to the distance between the nodes in the argument.

v= node which is currently being analysed

w= latest node in N'.

We complete the consequent iteration with this approach and continue until we find the least distances of all the nodes.

*In the table, D() calculates the distance of the node from any node.P() returns the previous node from which we calculate the distance.

With these prerequisites we start with the algorithm:

Here is the file:https://drive.google.com/open?id=1s2wtfLM7uAr5F-vzRgQKVUFAtbGI3npk

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.