Write a program to simulate the link-state algorithm (Table 20.2). Dijkstra's Algorithm ( ) // Initialization Tree

Write a program to simulate the link-state algorithm (Table 20.2).

Transcribed Image Text:

Dijkstra's Algorithm ( ) // Initialization Tree = {root} 3 I/ Tree is made only of the root 4. for (y = 1 to N) II N is the number of nodes { if (y is the root) 8. Dly] =0 // D[y] is shortest distance from root to node y else if (y is a neighbor) D[yl = c[root][y] Il c[x][y] is cost between nodes x and y in LSDB 10 11 else D[y]= 0 12 13 } 14 // Calculation 15 герeat 16 { 17 find a node w, with D[w]minimum among all nodes not in the Tree 18 Tree = Tree u {w} II Add w to tree // Update distances for all neighbors of w 19 20 for (every node x, which is a neighbor of w and not in the Tree) 21 D[x] = min {D[x], (D[w] + c[w][x])} 22 23 24 } until (all nodes included in the Tree) 25 } // End of Dijkstra