Q$4.(25$ marks$)$

$4\mathrm{.}1$ Apply the Dijkstra's algorithm to find the length of shortest response time path between the San

Francisco and New York in the below graph. For each step, show the values and the path of the

shortest path.

$4\mathrm{.}2$ If we want to find the shortest between the San Francisco and any other cities, we need to run

again the Dijkstra's algorithm from beginning or not? Please explain your answer and give an

example?