King Saud University Dijkstras Algorithm Report

This question is on the Dijkstra’s (Link State) algorithm. Show how the algorithm works by computing a table similar to Table 5.1 in the 7th edition of the textbook. (If you are using the 6th edition, that is Table 4.3). Use the word “infinity” (no letter capitalized), to indicate that the cost to some node is currently infinite. When a node is added to the N’ set, no more updates about the cost and predecessor should be done for this node; indicate this using two minus signs, i.e., “–“, in the table cells.

For example, if we have 4 nodes, w, x, y, and z, in a network as follows:

Consider the Dijkstra’s algorithm that is run at node z. The table will be like this:

Step	N’	D(x), p(x)	D(y), p(y)	D(w), p(w)
0	z	3, z	2, z	infinity
1	zy	3, z	—	4, y
2	zyx	—	—	4, y
3	zyxw	—	—	—

Consider the Dijkstra’s algorithm that is run at node y in the following network: