Shortest Path Problem (SPP) / Permasalahan Lintasan Terpendek
1. Pendahuluan
Lintasan terpendek merupakan lintasan minimum yang diperlukan untuk
mencapai suatu tempat dari tempat tertentu. Misalnya pada jaringan jalan raya yang
menghubungkan kota-kota di suatu wilayah. Dari jaringan jalan raya tersebut akan
dicari lintasan terpendek yang menghubungkan antara dua kota berlainan atau semua
lintasan terpendek masing-masing dari suatu kota ke setiap kota lainnya. Dengan
pemilihan lintasan terpendek ini, diharapkan dapat diperoleh efisiensi dari segi waktu
maupun biaya.
2. Metode Penyelesaian SPP
Secara umum, penyelesaian permasalahan lintasan terpendek dapat dilakukan
dengan menggunakan2 metode yaitu :
a. Metode konvensional, algoritma yang menggunakan perhitungan matematis
biasa. Ada beberapa metode konvensional yang biasa digunakan untuk
melakukan pencarian lintas/jalur terpendek yaitu algoritma Djikstraa,
Bellman_Ford dan Algoritma Floyd_warshall.
b. Metode heuristik. Ada beberapa algoritma pada metode heuristik yang biasa
digunakan dalam pencarian lintasan terpendek yaitu algoritma semut (ant
colony algorithm) dan algoritma genetika (genetic algoritm).
3. Terminologi Jaringan
Dalam permasalahan lintasan terpendek perlu dijelaskan terlebih dahulu
pengertian dari jaringan. Jaringan (network) adalah suatu susunan garis edar (path)
yang menghubungkan berbagai titik, dimana satu barang atau lebih akan bergerak
dari satu titik ke titik lain. Contoh dari jaringan dalam kehidupan sehari-hari
misalnya sistem jalan tol, jaringan telpon, jaringan rel kereta api, dan jaringan
televisi.
Jaringan diilustrasikan sebagai diagram yang terdiri dari dua
komponenpenting yaitu simpul (node) dan busur (link/arc). Node melambangkan
titik-titik persimpangan, sedangkan busur menghubungkan node-node tersebut dan
mencerminkan arus dari satu titik ke titik lain dalam jaringan tersebut. Node
dalam diagram jaringan dilambangkan dengan lingkaran dan busur dilambangkan
dengan garis yang menghubungkan simpul-simpul tersebut.
Jaringan yang ditunjukkan pada gambar 1 memiliki 5 node dan 10 busur.
Node 1 disebut sebagai titik awal dan 4 node lainnya merupakan tujuan,
tergantung dari apa yang ingin ditentukan dari jaringan tersebut. Sedangkan nilai-
nilai yang tertera pada tiap busur dapat menunjukkan informasi jarak, waktu atau
biaya.
Gambar 1. Jaringan yang terdiri dari kumpulan node dan busur
4. Langkah-Langkah Penyelesaian SPP dengan Algoritma Djikstraa
Langkah 1 : Memberi node 1 dengan permanen label [0, S]
Langkah 2 : Menghitung tentatif label (d, n) terhadap semua node yang dapat dicapai
langsung dari node 1. Dimana label d = jarak suatu node dengan node
sebelumnya dan n adalah node sebelumnya.
Langkah 3 : Mengidentifikasi seluruh node dengan tentatif label yang menunjukkan
jarak paling kecil dengan node sebelumnya. Misal node tersebut disebut
sebagai node k, maka ubahlah tentatif label pada node k tersebut
menjadi permanen label dengan menggunakan simbol [ , ]. Jika semua
node telah memiliki permanen label maka beralihlah ke langkah 5.
Langkah 4 : Memberi tentatif label (t,k) pada node yang dapat dicapai langsung dari
node k. Label t menunjukkan jarak kumulatif sedangkan k adalah node
sebelumnya yang telah memiliki permanen label. Apabila suatu node
telah memiliki tentatif label maka gunakanlah tentatif label yang
memiliki jarak terpendek.
Langkah 5 : Melakukan langkah-langkah diatas (langkah 3 dan 4) sampai seluruh
tentatif label pada tiap node memiliki jarak paling pendek dengan node
sebelumnya, sehingga tentatif label menjadi permanen label.
Tentukan jarak terpendek jaringan pada Gambar 1 jika node 1 sebagai titik asal dan
node 7 sebagai titik tujuan.
Gambar 1. Jaringan
Iterasi 1
Langkah 1: Memberi node 1 sebagai permanen label [0,S].
Langkah 2: Karena node 2, 3, dan 4 merupakan node yang secara langsung
berhubungan dengan node 1 maka masing-masing node tersebut diberi tentatif
label. Pada node 2 diberi tentatif label (4,1); (7,1) untuk node 3; dan (5,1)
untuk node 4.
Langkah 3: Node 2 merupakan tentatif label yang memiliki jarak terkecil
sehingga menjadi node dengan permanen label yang baru.
Hasil iterasi 1 pada langkah 2, 3, dan 4 dapat ditunjukkan pada Gambar 2.
(4,1)
[0,S]
(7,1)
(5,1)
Gambar 2. Hasil Iterasi 1
Langkah 4: Untuk setiap node dengan tentatif label yang berhubungan dengan
node 2 secara langsung (hanya dihubungkan 1 busur), dihitung panjang busur
dan dijumlah dengan jarak dari node 2 (4).
o Node 3: 3 + 4 = 7 (tidak lebih besar dari label saat ini yaitu (7,1)
sehingga jangan dirubah)
o Node 5: 5 + 4 = 9 (memberi tentatif label pada node 5 dengan (9,2))
[4,1] (9,2)
[0,S]
(7,1)
(5,1)
Gambar 3. Jaringan yang didapatkan dengan iterasi 1
Iterasi 2
Langkah 3: node 4 menjadi tentatif label dengan jarak terkecil (5). Sekarang
node 4 menjadi node dengan permanen label yang baru.
Langkah 4: Untuk setiap node 4 (hanya dihubungkan dengan 1 busur),
dihitung panjang busurnya dan dijumlah dengan jarak node 4.
o Node 3: 1 + 5 = 6 (node 3 diganti dengan tentatif label (6,4) karena
6<7, lebih kecil dari jarak sebelumnya.)
o Node 6: 8 + 5 = 13 (memberi tentatif label pada node 6 dengan (13,4))
Hasil iterasi 2 dapat dilihat pada Gambar 4 berikut :
[4,1] (9,2)
[0,S]
(6,4)
[5,1] (13,4)
Gambar 4. Jaringan yang didapatkan dengan iterasi 2
Iterasi 3
Langkah 3: node 3 menjadi tentatif label dengan jarak terkecil (6). Sekarang
node 3 menjadi node dengan permanen label yang baru.
Langkah 4: untuk setiap node dengan tentatif label yang berhubungan secara
langsung dengan node 3 (hanya dihubungkan dengan 1 busur) dihitung
panjang busurnya dan dijumlah dengan jarak node 3.
o Node 5: 2 + 6 = 8 (node 5 diganti dengan tentatif label (8,3) karena
8<9, Lebih kecil dari jarak sebelumnya.)
o Node 6: 6 + 6 = 12 (node 6 diganti dengan tentatif label (12,3), karena
12 < 13, lebih kecil dari jarak sebelumnya.)
[4,1] (8,3)
[0,S]
[6,4]
[5,1] (11,5)
Gambar 5. Jaringan yang didapatkan dengan iterasi 3
Iterasi 4
Langkah 3: node 5 menjadi tentatif label dengan jarak terkecil (8). Sekarang
node 5 menjadi node dengan permanen label yang baru.
Langkah 4: untuk setiap node dengan tentatif label yang berhubungan secara
langsung dengan node 5 (hanya dihubungkan dengan 1 busur) dihitung
panjang busurnya dan dijumlah dengan jarak node 5 (8).
o Node 6: 3 + 8= 11 (node 6 diganti dengan tentatif label (11,5) karena
11 < 12)
o Node 7: 6 + 8 = 14 (memberi tentatif label pada node 7 (14,5))
Gambar 6. menunjukkan hasil iterasi 4
Iterasi 5
Langkah 3: node 6 menjadi tentatif label dengan jarak terkecil (11). Sekarang
node 6 menjadi node dengan permanen label yang baru.
Langkah 4: untuk setiap node dengan tentatif label yang berhubungan secara
langsung dengan node 6 (hanya dihubungkan dengan 1 busur) dihitung
panjang busurnya dan dijumlah dengan jarak node 6 (11).
o Node 7: 2 + 11 = 13 (node 7 diganti dengan tentatif label (13,6) karena
13 < 14).
[4,1] [8,3]
[0,S] (14,5)
[6,4]
[5,1] (11,5)
Gambar 6. Jaringan yang didapatkan dengan iterasi 4
[4,1] [8,3]
[0,S] (13,6)
[6,4]
[5,1] [11,5]
Gambar 7. Jaringan yang didapatkan dengan iterasi 5
Iterasi 6
Langkah 3: node 7 menjadi permanen label dan sekarang semua node menjadi
permanen label. baru. Langkah selanjutnya adalah membuat kesimpulan pada
langkah 5.
Langkah 5: membuat kesimpulan dengan melihat kembali jarak terpendek dari
setiap permanen label. Solusi akhir untuk mendapatkan jaringan terpendek
dapat dilihat pada Gambar 17.13
Tabel 17.4 Solusi Akhir Contoh 3
Node Minimum distance Shortest route
2 4 1-2
3 6 1-4-3
4 5 1-4
5 8 1-4-3-5
6 11 1-4-3-5-6
7 13 1-4-3-5-6-7
[4,1] [8,3]
[0,S] [13,6]
[6,4]
[5,1] [11,5]
Gambar 17.13 Solusi optimal untuk jaringan dengan rute terpendek
Berdasarkan hasil perhitungan diatas, maka jarak terpendek yang dihasilkan
dari node 1 ke node 7 adalah sebesar 13 satuan jarak. Sedangkan rute yang
harus dilalui agar menghasilkan jarak terpendek ialah node 1 - 4 - 3 - 5 - 6 - 7.