Figure Q$1\mathrm{.}1$ shows a section of a road network in a major city consisting of $16$ nodes and about$24$ links. The travel time on each link $($in minutes$)$ is as depicted.a$)$ Find the route with the shortest path from Node $9$ to Node $15$ using Dijkstra algorithm byhand. Show all your work including a tabular summary of the steps and the final results. b$)$ Determine the route with the shortest time from Node $9$ to Node $15$ using a suitableoptimization software such as Matlab or EXCEL. Make sure to state the software used and why.Include all the input and output data in your report. c$)$ Due to congestion resulting from road construction works, the travel times on certain links hasdoubled as shown in Table Q$1\mathrm{.}1.$ Determine, the impact of construction works on travel timebetween node $9$ and node $15..$In your asnwers, clearly show all the appropriate steps you took to arrive at your answers in a$).$The inputs and outputs from the software used in b$)$ and c$)$ should also be documented in yourreport. Provide high quality tables$/$figures to depict your results in order to get top marks.