The following table is used to compute the shortest path from A to all other nodes...

   

Transcribed Image Text:

The following table is used to compute the shortest path from A to all other nodes in a network, according to the link-state algorithm, which is better known as Dijkstra's shortest path algorithm. Step N' D(v),P(v) D(w),P(w) D(x), P(x) D(y),P(y) D(z),P(z) 0 u Qu 5,u 1,u 1 ux 2.u 4,x 2,x 2 uxy 2u 3.y 4.Y 3 uxyv 3.y 4.y 4 4.Y uxyvw 5 uxyvwz a. Interpret the table above in your words: what it is showing and what are each row and each column showing? b. Consider the network shown in the following diagram. With the indicated link costs, use Dijkstra's shortest path algorithm to compute the shortest path from x to all other network nodes. Show how the algorithm works by computing a table like the one above. x 5 z 11 2 y 1 3 5 9 6 1 1 3 W 3 5 S The following table is used to compute the shortest path from A to all other nodes in a network, according to the link-state algorithm, which is better known as Dijkstra's shortest path algorithm. Step N' D(v),P(v) D(w),P(w) D(x), P(x) D(y),P(y) D(z),P(z) 0 u Qu 5,u 1,u 1 ux 2.u 4,x 2,x 2 uxy 2u 3.y 4.Y 3 uxyv 3.y 4.y 4 4.Y uxyvw 5 uxyvwz a. Interpret the table above in your words: what it is showing and what are each row and each column showing? b. Consider the network shown in the following diagram. With the indicated link costs, use Dijkstra's shortest path algorithm to compute the shortest path from x to all other network nodes. Show how the algorithm works by computing a table like the one above. x 5 z 11 2 y 1 3 5 9 6 1 1 3 W 3 5 S