Question $2$

$[10$ marks$]$

A$)$ Given the graph $\backslash (\backslash$mathrm$\{$G$\}=(\backslash$mathrm$\{$V$\},\backslash$mathrm$\{$E$\})\backslash )$ show $($highlight on the graph$)$ the Minimum Cost Spanning Tree and give its costs.

Answer: Cost $=$

Is it a unique MCST $($Yes$/$No$)?$

B$)$ Suppose you have a dense graph $\backslash ($ G $\backslash )$ with $\backslash ($ n $\backslash )$ vertices and $\backslash ($ m $\backslash )$ edges, where $\backslash (\backslash$mathbf$\{$m$\}>\backslash$mathbf$\{$n$\}\backslash ).$ The problem of finding the shortest path from every vertex to every other vertex $($all$-$pairs shortest paths$)$ can be solved either: i$)$ By running Dijkstra's Greedy algorithm $\backslash (\backslash$mathbf$\{$n$\}\backslash )$ times, each time starting from a different vertex, or ii$)$ By running Floyd's Dynamic Programming algorithm once.

Choose the most suitable algorithm$($s$)$ and data structure$($s$),$ and fill in the following table to justify your choice.

Answer: