Chapter $2$:

Q$2.($a$)$ Suppose Jenny would like to visit her friend in town $Z$ from her house at town

$O,$ but she might need to pass through towns $P,Q,R$ and $S.$ Therefore, she is

doing some study from Google map to get to know the distance between two

towns. The following table shows the distance $($in miles$)$ between two towns,

where a dash denotes there is no direct route connecting these two towns.

$($i$)$ Draw a network diagram for the given situation, where Jenny departs from

town $O$ to town $Z.$

$(5$ marks$)$

$($ii$)$ Find the shortest route and distance using Dijkstra algorithm. $(8$ marks$)$