Problem $2$: Use one of the following algorithms $($your choice$)$ Kruskal$$s$,$ Prim$$s$,$ or Dijkstra$$s to find

the minimum spanning tree $($Kruskal$$s or Prim$$s$),$ OR

the shortest path from a to any other node $($Dijkstra$$s$)$

in the following graph:

W$($ab$)=3$ W$($ac$)=4$ W$($ad$)=5$ W$($ae$)=1$ W$($bd$)=2$ W$($bf$)=1$

W$($bk$)=2$ W$($bl$)=5$ W$($cf$)=2$ W$($ck$)=5$ W$($de$)=4$ W$($df$)=2$

W$($dg$)=3$ W$($dh$)=5$ W$($gj$)=4$ W$($ef$)=3$ W$($ei$)=3$ W$($fg$)=3$

W$($fh$)=2$ W$($fk$)=1$ W$($gi$)=3$ W$($hk$)=7$

For the minimum spanning tree, draw the final tree and explicitly state its weight. Explain the algorithm used.

For the shortest path, show the final distance and path arrays in addition to the resulting spanning tree.