Short Path

Posted on

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.

 

 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s