PowerPoint Presentation

Teori GraphShortest Path Problem (Lintasan Terpendek)Disusun Oleh Kelompok 9 :Ghamal NasserRiyan Saputra IrawanM.Yuda Hendarto

Teori Graph Lintasan TerpendekPengertianPersoalan mencari lintasan terpendek di dalam graf merupakan salah satu persoalan optimasi. Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya.Asumsi yang digunakan di sini adalah bahwa semua bobot bernilai positif. Lintasan terpendek adalah jalur yang dilalui dari suatu node ke node lain dengan besar atau nilai pada sisi yang jumlah akhirnya dari node awal ke node akhir paling kecil. Macam-Macam Masalah Lintasan Terpendek

Lintasan terpendek antara dua buah simpul tertentu (a pair shortestpath).

Lintasan terpendek antara semua pasanggan simpul (all pairs shortestpath).

Lintasan terpendek dari simpul tertentu ke semua simpul yang lain(single-source shortest path).

Lintasan terpendek antara dua buah simpul yang melalui beberapasimpul tertentu (intermediate shortest path).

AEBCD5m3m6m7m9mDapat diketahui :Himpunan SimpulV ={A,B,C,D,E}Himpunan Sisi E ={ (A,B),(A,C),(B,E),(C,D),(D,E) } =( e1,e2,e3,e4,e5 }

Node-Node : A,B,C,D,EBobot (dalam jarak) antar setiap node : e1=5m, e2=3m, e3=9m, e4=6m, e5=7mAlgoritma Lintasan TerpendekAlgoritma Greedy

Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah, pada setiap langkah :

Mengambil pilihan yang terbaik yang dapat diperoleh saat itu

b. Berharap bahwa dengan memilih optimum local pada setiap langkah akan mencapai optimum global. Algoritma greedy mengasumsikan bahwa optimum lokal merupakan bagian dari optimum global. Langkah-Langkah Algoritma GreedyPeriksa semua sisi yang langsung bersisian dengan simpul a. Pilih sisi yang bobotnya terkecil.Sisi ini menjadi lintasan terpendek pertama, sebut saja L(1). Hitung : d(i) = panjang L(1) + bobot sisi dari simpul akhir L(1) ke simpul i yang lain pilih d(i) yang terkecil Bandingkan d(i) dengan bobot sisi (a, i). Jika bobot sisi (a, i) lebih kecil daripada d(i), maka L(2) = L(1) U (sisi dari simpul akhir L(i) ke simpul i) Dengan cara yang sama, ulangi langkah 2 untuk menentukan lintasan terpendek berikutnya. Kelebihan Algoritma Greedy

Prinsip Seleksi berguna untuk menentukan jalan tersingkat,sehingga kita dapat menuju tujuan tepat waktu.

Hasil analisis berdasarkan bobot-bobot yang berbeda,menunjukan bahwa semakin banyak bobot yang di berikan,maka semakin akurat pula data yang dihasilkan.Sehingga menghasilkan waktu yang efisien.

Kekurangan Algoritma Greedy

Tidak beroperasi menyeluruh terhadap semua alternatif solusi yang ada.

Pemilihan fungsi seleksi : mungkin saja beberapa fungsi seleksi berbeda sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma bekerja dengan benar dan menghasilkan solusi yang benar-benar optimum,oleh karena itu algoritma greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum.Studi Kasus dengan Algoritma GreedyInisial NodeNama TempatARumah DikaBKantor PosCKantor PolisiDToko Emas SuburETaman AnggrekFBank Amanah UmmahGToko Baju GalangHMuseum AstronomiIRumah Sakit PertiwiCarilah Lintasan Terpendek Dari RUMAH DIKA ke RUMAH SAKIT PERTIWI jika Diketahui :ABCDEFIHG0,45km0,5km0,3km0,55km1,85km0,35km0,75km0,35km0,35km0,7km0,4km0,25kmGraph Rumah Dika Rumah Sakit PertiwiPerhitungan Algoritma GreedyTitik Awal : L(1)= bobot A-B,karena bobot (A-B < A-C)= 0,45Km(A-B)L(n)Bobot L(n)Total Bobot d(1)Total Bobot d(2)KondisiLintasan Terpilih10,450,45 + Bobot (B-D)= 0,45+0,3= 0,750,45 + Bobot (B-H)= 0,45+1,85= 2,3d(1)