Masalah Rute Terpendek
Menyangkut suatu
jaringan tersambung pada umumnya dikaitkan dengan : biaya perjalanan minimum
atau jarak minimum.
Satu simpul sebagai
sumber dan Simpul lain disebut tujuan.
Tujuan
dari model ini adalah mencari suatu lintasan yang
menghubungkan sumber dan tujuan sedemikian sehingga total biaya atau jarak yang
ditempuh dalam perjalanannya minimum.
Masalah
rute terpendek dapat diselesaikan dengan algoritma sbb:
1.
Buat suatu daftar induk dalam bentuk tabel
dari cabang-cabang yang masuk padanya dibawah simpul dalam urutan biaya
menurun. Hilangkan dari daftar ini cabang-cabang yang mempunyai sumber sebagau
simpul keduanya.
2.
Beri tanda (*) pada sumber dengan harga
0, kemudian pilih cabang termurah yang masuk pada sumber tersebut dan lingkari
cabang tersebut. Hilangkan dari daftar ini cabangcabang yang memiliki simpul
yang baru diberi tanda (*) sebagai simpul keduanya.
3.
Jika simpul yang baru dibintangi ini
merupakan tujuan, maka lanjutkan ke langkah 5.
4.
Tinjau semua simpul yang dibintangi yang
memiliki cabangcabang yang tak dilingkari dibawahnya.
5.
Z* adalah harga yang ditetapkan untuk
tujuan, lintasan dengan biaya minimum diperoleh secara rekursif yang bermula
dari tujuan dengan menyertakan dalam lintasan ini setiap cabang yang dilingkari
yang simpul keduanya kepunyaan lintasan.
Contoh:
Seorang pekerja yang
tinggal di Kota A bertujuan untuk mencari jalur terpendek yang akan
meminimumkan waktu perjalanan menuju kota F. Pekerja tersbut telah mencatat
waktu perjalanan dalam menit sepanjang jalan raya yang berbeda di antara kedua
kota. Data selengkapnya dapat dilihat pada tabel berikut ini: (Sel kosong
menunjukkan tidak ada jalan raya yang menghubungkan
kedua kota tersebut)
|
|
Kota A
|
Kota B
|
Kota C
|
Kota D
|
Kota E
|
Kota F
|
|
Kota A
|
|
18
|
|
32
|
|
|
|
Kota B
|
18
|
|
12
|
28
|
|
|
|
Kota C
|
|
12
|
|
17
|
|
32
|
|
Kota D
|
32
|
28
|
17
|
|
4
|
17
|
|
Kota E
|
|
|
|
4
|
|
11
|
|
Kota F
|
|
|
32
|
17
|
11
|
|
Penyelesaian:
1.
Langkah kesatu , Buat daftar induk sbb:
|
A
|
B
|
C
|
D
|
E
|
F
|
|
AB=18
|
BC=12
|
CB=12
|
DE=4
|
ED=4
|
FE=11
|
|
AD=32
|
BD=28
|
CD=17
|
DF=17
|
EF=11
|
FD=17
|
|
|
|
CF=32
|
DC=17
|
|
FC=32
|
|
|
|
|
DB=28
|
|
|
2.
Langkah Kedua
a. Bintangi
simpul sumber A dan tetapkan nilai 0
b. Cabang
terkecil pada sumber A adalah AB, lalu bintangi B dan beri nilai 18
c. Lingkari
AB dan hilangkan semua cabang yang simpul keduanya B yaitu CB dan DB.
d. Maka
daftar induk yang baru adalah:
|
A*(0)
|
B*(18)
|
C
|
D
|
E
|
F
|
|
AB=18
|
BC=12
|
CD=17
|
DE=4
|
ED=4
|
FE=11
|
|
AD=32
|
BD=28
|
CF=32
|
DF=17
|
EF=11
|
FD=17
|
|
|
|
|
DC=17
|
|
FC=32
|
3.
Langkah Ketiga
a. Simpul
yang dibintangi adalah A dan B
b. Lakukan
penjumlahan 0+ 32=32 di bawah A yang diperoleh dari penjumlahan nilai A dengan
cabang AD, dan 18+12=30 di bawah B yang diperoleh dari penjumlahan nilai B
dengan BC.
c. 30
nilai paling kecil yang diperoleh dari penjumlahan, maka bintangi C dengan
nilai 30 dan lingkari BC.
d. Hilangkan
semua cabang yang simpul keduanya C, yaitu DC, FC kecuali cabang yang
dilingkari.
|
A*(0)
|
B*(18)
|
C*(30)
|
D
|
E
|
F
|
|
AB=18
|
BC=12
|
CD=17
|
DE=4
|
ED=4
|
FE=11
|
|
AD=32
|
BD=28
|
CF=32
|
DF=17
|
EF=11
|
FD=17
|
4.
Lanngkah Keempat
a. Simpul
yang dibintangi adalah A, B dan C.
b. Lakukan
penjumlahan 0+ 32=32 di bawah A , 18+28=46 di bawah B serta 30 + 17 = 47 di
bawah C.
c. 32
nilai paling kecil yang diperoleh dari penjumlahan, maka bintangi D dengan
nilai 32 dan lingkari AD.
d. Hilangkan
semua cabang yang simpul keduanya D, yaitu CD, ED, FD.
e. Seperti
daftar induk yang baru berikut:
|
A*(0)
|
B*(18)
|
C*(30)
|
D*(32)
|
E
|
F
|
|
AB=18
|
BC=12
|
CF=32
|
DE=4
|
EF=11
|
FE=11
|
|
AD=32
|
|
|
DF=17
|
|
FD=17
|
5.
Langkah Kelima
a. Simpul
yang dibintangi adalah A, B, C, D
b. Lakukan
penjumlahan 18+28=46 di bawah B serta 30 + 32 = 62 dibawah C, 32 + 4= 36 di
bawah D.
c. 36
nilai paling kecil yang diperoleh dari penjumlahan, maka bintangi E dengan
nilai 36 dan lingkari DE.
d. Hilangkan
semua cabang yang simpul keduanya E, yaitu FE.
|
A*(0)
|
B*(18)
|
C*(30)
|
D*(32)
|
E*(36)
|
F
|
|
AB=18
|
BC=12
|
CF=32
|
DE=4
|
EF=11
|
|
|
AD=32
|
|
|
DF=17
|
|
|
6.
Langkah Keenam
a. Simpul
yang dibintangi adalah A, B, C, D, E.
b. Lakukan
penjumlahan 30 + 32 = 62 dibawah C, 32 + 17= 49 di bawah D, dan 36 + 11 = 47 di
bawah E.
c. 47
nilai paling kecil yang diperoleh dari penjumlahan, maka bintangi F dengan
nilai 47 dan lingkari EF.
d. Hilangkan
semua cabang yang simpul keduanya , yaitu CF, DF.
|
A*(0)
|
B*(18)
|
C*(30)
|
D*(32)
|
E*(36)
|
F*(47)
|
|
AB=18
|
BC=12
|
|
DE=4
|
EF=11
|
|
|
AD=32
|
|
|
|
|
|
Karena tidak ada lagi
cabang yang perlu dianalisis, maka iterasi selesai dengan Z* = 47.
Kesimpulan:
Waktu optimum yang dibutuhkan
untuk perjalanan dari Kota A ke Kota F adalah 47 menit dengan rute AD, DE, EF
