CptS 455, Homework for Chapters 4 and 5

3, 12, 21, 29, 37, 38, 44

Problems from textbook Chapter 5:

4, 7, 9

Use the link-state algorithm (Dijkstra's alg.) to complete the following table to find a least-cost path between node A and every other node in the graph below.

Step	Stable	Dist(B),Pred(B)	Dist(C),Pred(C)	Dist(D),Pred(D)	Dist(E),Pred(E)
-1		inf	inf	inf	inf
0	A	1,A	2,A	inf	inf
1	AB	1,A	2,A	16,B	6,B
...

The graph to use is described by the following edge list: (AB, 1), (AC, 2), (BD, 15), (BE, 5), (CE, 2), (CD, 1), (DE, 10). It may help to draw the graph first.

When the table is complete, list the least-cost paths it describes from A to each of the other nodes (i.e., list the nodes in each path and the path cost).