Question $4(25$ marks$)$

The distance between the cities is given in a logistics network between several cities as shown in$.$ Figure Q$4$ below.

$($a$)$ The goods need to be shipped from City A to City G$,$ determine the shortest path in a Stepwise manner based on the use of the Dijkstra algorithm.

$(10$ marks$)$

$($b$)$ Indicate all the possible shortest path$($s$)$ and the minimum total distance.

$(5$ marks$)$

$($c$)$ Assume the logistics network is an undirected graph. Draw the Minimum Spanning Tree based on the above network and explain what the Minimum Spanning Tree is$.(5$ marks$)$

$($d$)$ Clarify the differences between Prim's algorithm and Kruskal's algorithm. $(5$ marks$)$