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

Question

The following table is used to compute the shortest path from A to all other nodes in a network, according to link-state 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

2,u

5,u

1,u

?

?

1

ux

2,u

4,x

  

2,x

?

2

uxy

2,u

3,y

  

  

4,y

3

uxyv

3,y

  

  

4,y

4

uxyvw

  

  

   

  

4,y

5

uxyvwz

   

  

  

  

   

a. Interpret the table in your own words.

b. Consider the following network. With the indicated link costs, use Dijkstra's shortest-path algorithm to compute the shortest path from x to all network nodes. Show how the algorithm works by computing a table similar to the table above.

Step

N.

D(v),P(v)

D(w),P(w)

D(x),P(x)

D( y),P( y)

D(z),P(z)

0

u

2,u

5,u

1,u

?

?

1

ux

2,u

4,x

  

2,x

?

2

uxy

2,u

3,y

  

  

4,y

3

uxyv

3,y

  

  

4,y

4

uxyvw

  

  

   

  

4,y

5

uxyvwz

   

  

  

  

   

Explanation / Answer

x y z w u t v s x 0 5x 1x 2x w 5x 1x 2x 3w u 3u 2x 3w v 3u 5v 3w 5v t 3u 5t 5v 5v y 4y 5v 5v z 4y

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.