a. Lintasan Terpendek (Shortest Path)
graf berbobot (weighted graph),
lintasan terpendek: lintasan yang memiliki total bobot minimum.
Contoh aplikasi:
1.Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota
2.Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer.
Terdapat beberapa jenis persoalan lintasan terpendek, antara lain:
a.Lintasan terpendek antara dua buah simpul tertentu.
b.Lintasan terpendek antara semua pasangan simpul.
c.Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
d.Lintasan terpendek abtara dua buah simpul yang melalui beberapa simpul tertentu.
==> Di dalam kuliah ini kita memilih jenis persoalan 3.
Uraian persoalan
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.
Algoritma menentukan lintasan terpendek yang terkenal: algoritma Dijkstra
Properti algoritma Dijkstra:
1. Matriks ketetanggaan M[mij]
mij = bobot sisi (i, j) (pada graf tak-berarah mij = mji )
mii = 0
mij = , jika tidak ada sisi dari simpul i ke simpul j
2. Larik S = [si] yang dalam hal ini,
si = 1, jika simpul i termasuk ke dalam lintasan terpendek
si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek
3. Larik/tabel D = [di] yang dalam hal ini,
di = panjang lintasan dari simpul awal s ke simpul i
Algoritma Lintasan Terpendek Dijkstra
(Mencari lintasan terpendek dari simpul a ke semua simpul lain }
Langkah 0 (inisialisasi):
- inisialisasi si = 0 dan di = mai untuk i = 1, 2, ..., n
Langkah 1:
- isi sa dengan 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi sudah pasti terpilih)
- isi da dengan (tidak ada lintasan terpendek dari simpul a ke a)
Langkah 2, 3, ..., n-1:
- cari j sedemikian sehingga sj = 0 dan dj = min{d1, d2, ..., dn}
- isi sj dengan 1
perbarui di, untuk i = 1, 2, 3, …, n dengan:
di (baru) = min{di (lama), dj + mji }.
Jadi, lintasan terpendek dari:
1 ke 3 adalah 1, 3 dengan panjang = 10
1 ke 4 adalah 1, 3, 4 dengan jarak = 25
1 ke 2 adalah 1, 3, 4, 2 dengan jarak = 45
1 ke 5 adalah 1, 5 dengan jarak = 45
1 ke 6 tidak ada
Contoh 6.34. Tinjau graf berarah pada Gambar 6.50 yang menyatakan jarak beberapa kota di Amerika Serikat.
Jadi, lintasan terpendek dari:
5 ke 6 adalah 5, 6 dengan panjang = 250
5 ke 7 adalah 5, 6, 7 dengan jarak = 1150
5 ke 4 adalah 5, 6, 4 dengan jarak = 1250
5 ke 8 adalah 5, 6, 8 dengan jarak = 1650
5 ke 3 adalah 5, 6, 4, 3 dengan jarak = 2450
5 ke 2 adalah 5, 6, 4, 3, 2 dengan jarak = 3250
5 ke 1 adalah 5, 6, 8, 1 dengan jarak = 3350
