Interactive end-of-chapter exercises


Supplement to Computer Networking: A Top Down Approach 8th Edition


"Tell me and I forget. Show me and I remember. Involve me and I understand." Chinese proverb

Textbook Cover

Dijkstra's Link State Algorithm (for computing least cost paths)

Consider the 6-node network shown below, with the given link costs.


Using Dijkstra's algorithm, find the least cost path from source node U to all other destinations and answer the following questions



Question List


1. What is the shortest distance to node x and what node is its predecessor? Write your answer as n,p

2. What is the shortest distance to node v and what node is its predecessor? Write your answer as n,p

3. What is the shortest distance to node u and what node is its predecessor? Write your answer as n,p




Solution


1. The minimum distance from node u to node x is 4, and node x's predecessor is node u. The full answer was: 4,u

2. The minimum distance from node u to node v is 8, and node v's predecessor is node w. The full answer was: 8,w

3. The minimum distance from node u to node u is 0, and node u's predecessor is node u. The full answer was: 0,u



That's incorrect

That's correct

The answer was: 4,u

Question 1 of 3

The answer was: 8,w

Question 2 of 3

The answer was: 0,u

Question 3 of 3

Try Another Problem

We gratefully acknowledge the programming and problem design work of John Broderick (UMass '21), which has really helped to substantially improve this site.

Copyright © 2010-2021 J.F. Kurose, K.W. Ross
Comments welcome and appreciated: kurose@cs.umass.edu