Short Path

Graf Berbobot

Aplikasi Graf

Lintasan Terpendek (Shortest Path)

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

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”