Short Path

Graf Berbobot

• Graf berbobot adalah graf yang setiap sisinya diberi sebuah bobot
• Contoh:

Aplikasi Graf

Lintasan Terpendek (Shortest Path)

• Graf berbobot (weighted graph)
• Lintasan terpendek: lintasan yang memiliki total bobot minimum.

Contoh aplikasi:

• Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota
• Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer.

Lintasan Terpendek

• Terdapat beberapa jenis persoalan lintasan terpendek, antara lain:
  • Lintasan terpendek antara dua buah simpul tertentu.
  • Lintasan terpendek antara semua pasangan simpul.
  • Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
  • Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
• Di dalam kuliah ini kita memilih jenis persoalan 3
• Diberikan graf berbobot G = (V, E) dan sebuah simpul a.
• Tentukan lintasan terpendek dari a ke setiap simpul lainnya di G.
• Asumsi yang kita buat adalah bahwa semua sisi berbobot positif.
• Untuk menentukan lintasan terpendek dari suatu graf berbobot dapat digunakan
  • Algoritma Djikstra
  • Algoritma Hapus

Algoritma Djikstra

• Algoritma Djikstra adalah sebuah prosedur iteratif yang mencari lintasan terpendek antara a dan z dalam graf dengan pembobot.
• Prosesnya dengan cara mencari panjang lintasan terpendek dari sebuah simpul pendahulu dan menambahkan simpul-simpul tersebut ke set simpul S.
• Algoritma berhenti setelah mencapai simpul z.

Contoh Algoritma Djikstra

• Tentukan lintasan terpendek dari a ke z

Solusi

• Mulai dari simpul A (lingkari) sebagai simpul awal
• Tentukan jalur dengan bobot terpendek yang menghubungkan A dengan simpul yang lain.
• Jika jalurnya lebih dari satu, pilih jalur dengan bobot terendah

• Lingkari Simpul C
• Tentukan jalur dengan bobot terpendek yang menghubungkan C dengan simpul yang lain.
• Jika jalurnya lebih dari satu, pilih jalur dengan bobot terendah

• Lingkari Simpul B
• Tentukan jalur dengan bobot terpendek yang menghubungkan B dengan simpul yang lain.
• Jika jalurnya lebih dari satu, pilih jalur dengan bobot terendah

  

• Lingkari Simpul D
• Tentukan jalur dengan bobot terpendek yang menghubungkan D dengan simpul yang lain.
• Jika jalurnya lebih dari satu, pilih jalur dengan bobot terendah

  

• Lingkari Simpul E
• Tentukan jalur dengan bobot terpendek yang menghubungkan E dengan simpul yang lain.
• Jika jalurnya lebih dari satu, pilih jalur dengan bobot terendah

   

  

• Jadi Lintasan terpendek dari A ke Z adalah

  

• ACBDEZ
• Dengan Bobot = 2 + 1 + 5 + 2 + 3 = 13

Algoritma TKD (Hapus)

• Algoritma hapus merupakan salah satu algoritma atau cara untuk memperoleh jalur terpendek dari sebuah graf berbobot. Langkah-langkah yang dilakukan untuk menggunakan algoritma hapus adalah sebagai berikut.
  • Tentukan simpul awal
  • Hapus, sisi-sisi dengan bobot paling tinggi dengan syarat jika sisi-sisi ini dihapus graf awal tidak terbagi menjadi dua bagian atau lebih (graf tidak terpisah).
  • Proses penghapusan sisi selesai setelah tidak ada lagi sisi yang dapat di hapus
• Tentukan Lintasan Terpendek dari A ke F dengan Algoritma “Hapus”

• Jadi Lintasan terpendek dari A ke Z adalah

• ACBDEZ
• Dengan Bobot = 2 + 1 + 5 + 2 + 3 = 13

Soal Latihan

• Tentukan panjang jalur terpendek dari A ke F dengan menggunakan Algoritma Djikstra dan “Hapus”

Untuk lebih jelasnya silahkan download link berikut ini:

Terimakasih atas perhatiannya.

Untuk materi sebelumnya tentang Pewarnaan Graf, silahkan Klik Disini.

Untuk materi selanjutnya tentang Kode Huffman, silahkan Klik Disini.