Analytics Modelling: Problem Assignment

$6$

$3.$ In the following, $s_1,$dots,$s_8$ are the digits of the relevant student number for this

$[35]$

question. They are used for some edge weights in Figure $1$ below. If any $s_i=0,$ then set that $s_i$:$=5.$ For example, if $s_3=0,$ then set $s_3$ to $5,$ meaning that the edge $4-5$ in Figure $1$ will have length $5.$

Figure $1$ represents the road system in the town Marawatna, with streets being edges and street junctions being vertices. The number on each street is the length of the street in hundreds of metres. Traffic can travel in either direction along any street. The Hospital is located at the junction marked $1.$

$($a$)$ To improve ambulance service quality, you are asked to find a shortest path from the Hospital to vertex $11,$ and its length. Solve this problem, using an appropriate algorithm. Show all of your work, including the resulting shortest path spanning tree rooted at the Hospital.

From your work, what $-$ if anything $-$ can you say about the shortest path from vertex $3$ to vertex $11$ ; or the shortest path from vertex $3$ to vertex $7?$ Explain your thinking.

$($b$)$ The Marawatna Town Council wish to install a new traffic light system, which will replace the existing traffic light at each junction in the town. This will involve connecting all of the junctions together by a system of electrical cables. Cables must be laid along existing streets to allow access for maintenance. The