$(30$ points$)($Greedv technique$)$ Ali would like to go on a long holiday visiting number of

cities in Turkex, He will start his joumex from Istanbul. The duration of journeys with a

bus between cities are given as below:

$$stanbul$-$ Ku$$adas$(5$ hours$)$

Ku$$adas$-$ Bodrum $(2$ hours$)$

$$stanbul$-$ Eski$$ehir $(3$ hours$)$

Eski$$ehir$-$ Nev$$ehir $(5$ hours$)$

Bodrum$-$ Mersin $(12$ hours$)$

Mersin$-$ Antalya $(7$ hours$)$

Antalya$-$ Nev$$ehir $(6$ hours$)$

Mersin$-$ Nev$$ehir $(3$ hours$)$

Eski$$ehir$-$Mersin $(7$ hours$)$

$$stanbul$-$Mersin $(9$ hours$)$

Bodrum$-$ Eski$$ehir $(7$ hours$)$

He needs to visit Ku$$adas$,$ Bodrum, Eski$$ehir$,$ Nev$$ehir$,$ Mersin, Antalya starting from

Istanbul.

Draw a Graph with vertices denoted bx cities, and the edges between cities are the

duration of bus trips mentioned above.

Draw the Minimum Spanning Tree

a$.$ Using Prim's algorithm

b$.$ Using Kruskal's algarithm

Show your steps,

Draw the single source shortest paths $($starting from Istanbul$)$ using Diikstra

Algorithm. Show your steps. Is the MST you have found the same as the single

source shortest path xou have found with Dijkstra?