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.
