Consider the network shown in Problem P26. Using Dijkstra’s algorithm, and showing your work using a table similar to Table 4.3, do the following:
a. Compute the shortest path from t to all network nodes.
b. Compute the shortest path from u to all network nodes.
c. Compute the shortest path from v to all network nodes.
d. Compute the shortest path from w to all network nodes.
e. Compute the shortest path from y to all network nodes.
f. Compute the shortest path from z to all network nodes.
Refer the Dijkstra’s algorithm and the problem 26 in the text book.
a)
The shortest path from t to all network nodes:
Num |
N’ |
D(u),p(u) |
D(v),p(v) |
D(w),p(w) |
D(x),p(x) |
D(y),p(y) |
D(z),p(z) |
0 |
t |
2,t |
4,t |
7,t |
|||
1 |
tu |
2,t |
4,t |
5,u |
7,t |
||
2 |
tuv |
2,t |
4,t |
5,u |
7,v |
7,t |
|
3 |
tuvw |
2,t |
4,t |
5,u |
7,v |
7,t |
|
4 |
tuvwx |
2,t |
4,t |
5,u |
7,v |
7,t |
15,x |
5 |
tuvwxy |
2,t |
4,t |
5,u |
7,v |
7,t |
15,x |
6 |
tuvwxyz |
2,t |
4,t |
5,u |
7,v |
7,t |
15,x |
Here, assume N'=subset of nodes, D(v)= The path from the source to the destination for the node,v. p(v)=The path with least cost from source to node, v.
b)
The shortest path from u to all network nodes:
Num |
N’ |
D(t),p(t) |
D(v),p(v) |
D(w),p(w) |
D(x),p(x) |
D(y),p(y) |
D(z),p(z) |
0 |
u |
2,u |
3,u |
3,u |
|||
1 |
ut |
2,u |
3,u |
3,u |
9,t |
||
2 |
utv |
2,u |
3,u |
3,u |
6,v |
9,t |
|
3 |
utvw |
2,u |
3,u |
3,u |
6,v |
9,t |
|
4 |
utvwx |
2,u |
3,u |
3,u |
6,v |
9,t |
14,x |
5 |
utvwxy |
2,u |
3,u |
3,u |
6,v |
9,t |
14,x |
6 |
utvwxyz |
2,u |
3,u |
3,u |
6,v |
9,t |
14,x |
c)
The shortest path from v to all network nodes:
Num |
N’ |
D(t),p(t) |
D(u),p(u) |
D(w),p(w) |
D(x),p(x) |
D(y),p(y) |
D(z),p(z) |
0 |
v |
4,v |
3,v |
4,v |
3,v |
8,v |
|
1 |
vx |
4,v |
3,v |
4,v |
3,v |
8,v |
11,x |
2 |
vxu |
4,v |
3,v |
4,v |
3,v |
8,v |
11,x |
3 |
vxut |
4,v |
3,v |
4,v |
3,v |
8,v |
11,x |
4 |
vxutw |
4,v |
3,v |
4,v |
3,v |
8,v |
11,x |
5 |
vxutwy |
4,v |
3,v |
4,v |
3,v |
8,v |
11,x |
6 |
vxutwyz |
4,v |
3,v |
4,v |
3,v |
8,v |
11,x |
d)
The shortest path from w to all network nodes:
Step |
N’ |
D(t),p(t) |
D(u),p(u) |
D(v),p(v) |
D(x),p(x) |
D(y),p(y) |
D(z),p(z) |
0 |
w |
|
3,w |
4,w |
6,w |
||
1 |
wu |
5,u |
3,w |
4,w |
6,w |
||
2 |
wuv |
5,u |
3,w |
4,w |
6,w |
12,v |
|
3 |
wuvt |
5,u |
3,w |
4,w |
6,w |
12,v |
|
4 |
wuvtx |
5,u |
3,w |
4,w |
6,w |
12,v |
14,x |
5 |
wuvtxy |
5,u |
3,w |
4,w |
6,w |
12,v |
14,x |
6 |
wuvtxyz |
5,u |
3,w |
4,w |
6,w |
12,v |
14,x |