Anggota Kelompok:1) Fembi Rekrisna Grandea Putra (M0513019)2) Maulana Aziz A. A. L. (M0513029)3) Rizal Choiri Ramadhon (M0513041)

1. Problem 1: Find the shortest path from Arad to Budapest

– Dijkstra Algorithm for Traveling in Rumania Keterangan : Nama kota menggunakan inisial huruf pertama.Langkah-langkah menggunakan Algoritma Djikstra untuk graf tersebut adalah sebagai berikut :1. L (a )=0L (a )=L ( z )=L (o )=L ( s )=L (f )=L ( t )=L ( l )=L (m)=L (d )=L ( c )=L (r )=L (p )=L (b )=∞

2. Adj dengan a adalah z , s , tL ( z)=min(L ( z ) , L (a )+za¿)=min(∞ ,0+¿75)=75¿¿L (s )=min(L ( s ) , L (a )+sa¿)=min(∞,0+¿140)=140 ¿¿L ( t )=min(L ( t ) , L (a )+ta¿)=min(∞ ,0+¿118)=118 ¿¿

3. Adj dengan z adalah oL (o )=min(L (o ) , L ( z )+oz¿)=min (∞ ,75+¿71)=146¿¿

4. Adj dengan o adalah sL (s )=min(L ( s ) , L (o )+so ¿)=min(140,146+¿151)=140 ¿¿

5. Adj dengan t adalah lL ( l )=min(L ( l ) , L ( t )+¿¿)=min(∞,118+¿111)=229¿¿

6. Adj dengan l adalah mL (m )=min(L (m ) , L (l )+ml¿)=min(∞ ,229+¿70)=299¿¿

7. Adj dengan m adalah dL (d )=min(L (d ) , L (m )+dm¿)=min(∞ ,299+¿75)=374 ¿¿

8. Adj dengan d adalah cL (c )=min(L (c ) , L (d )+cd ¿)=min(∞ ,374+¿120)=494 ¿¿

9. Adj dengan c adalah r dan pL (r )=min (L (r ) , L (c )+rc¿)=min(∞, 494+¿146)=640 ¿¿L ( p )=min(L ( p ) , L (c )+ pc¿)=min(∞ ,494+¿138)=632¿¿

10. Adj dengan s adalah f dan rL ( f )=min(L ( f ) , L ( s )+ fs¿)=min(∞ ,140+¿99)=239¿¿L (r )=min (L (r ) , L (s )+rs¿)=min(640,140+¿80)=220 ¿¿

11. Adj dengan f adalah bL (b )=min(L (b ) , L ( f )+bf ¿)=min(∞,239+¿211)=450 ¿¿

12. Adj dengan r adalah c dan pL (c )=min(L (c ) , L (r )+cr¿)=min(494,220+¿146)=366 ¿¿L ( p )=min(L ( p ) , L (r )+ pr¿)=min(632,220+¿97)=317 ¿¿

13. Adj dengan p adalah bL (b )=min(L (b ) , L ( p )+bp¿)=min(450,317+¿101)=418 ¿¿

Jadi bentuk grafnya adalah sebagai berikut :

OPTIMAL :L (a )=0L ( z )=75L (s )=140L ( t )=118L (o )=146L ( l )=229L (m )=299L (d )=374

L (c )=366L ( f )=239L (r )=220L (p )=317L (b )=418

Jalur yang diambil adalah L (a )→L (s )→L (r )→L (p )→L (b )=418Untuk kota Neamt, Iasi, Vaslui, Urziceni, Hirsova, Eforie, Giurgiu tidak dimasukkan karena kota yang dituju telah tercapai.

– Non Dijkstra Algorithm for Traveling in RumaniaAlgoritma Non Dijkstra dalam hal ini adalah algoritma Greedy. Jadi jalur grafnya adalah sebagai berikut:Cari kota yang paling banyak, dengan algoritma GreedyCari jalan yang paling pendek, dengan MSTperbyandingan peringkat.

2. Problem 2: Find a minimum-value path but passed through more of the city of Arad to Budapest (Note: One of the city can be crossed only once)

Menggunakan algoritma Kruskal atau MST (Minimum Spanning Tree) dengan ciri-ciri sebagai berikut :1) Bobot minimal2) Memuat semua vertex3) Graf tanpa sirkuit

Berikut ini urutan bobot minimal ke maksimal yang memuat semua vertex dengan membentuk graf tanpa sirkuit :70 = l – m71 = z – o75 = a – z dan m – d80 = s – r85 = b – u86 = h – e87 = n – l90 = b – g92 = l – v97 = r – p98 = u – h99 = s – f101 = p – b111 = t – l118 = a – t120 = d – c138 = c – p142 = u – v

Sehingga membentuk graf sebagai berikut :