Penyelesaian Masalah dengan Algoritma
Djikstra
Dosen Pembimbing : Adhika P., S.
Kom
Oleh : Siti Qomariyah
(Prodi TI / 2120150034)
Universitas Nahdlatul Ulama Sunan
Giri Bojonegoro
(UNUGIRI)
A.
ABSTRAK
Paper
ini membahas tentang persoalan lintasan terpendek suatu graf dengan algoritma djikstra.
Lintasan terpendek merupakan bagian dari teori graf. Jika diberikan sebuah graf
berbobot, masalah jarak terpendek adalah bagaimana kita mencari sebuah jalur
pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut.
Persoalan ini adalah persoalan optimasi, dimana kita akan mencari solusi
penyelesaian yang paling efektif dari masalah penentuan lintasan terpendek pada
suatu graf.
Saat
ini banyak sekali algortima-algoritma yang dapat digunakan untuk menyelesaikan
persoalan penentuan lintasan terpendek (shortest path problem) dari suatu graf.
Solusi yang didapat dari penelusuran algoritma tersebut dapat diberi nama
Pathing Algorithm. Ada dua algortima yang cukup terkenal yang bisa digunakaan untuk
menyelesaikan persoalan lintasan terpendek, yaitu Algoritma Djikstra dan
Algoritma Bellman-Ford. Tetapi pada kesempatan ini kita hanya akan membahas
tentang algoritma dijkstra.
Algoritma
Dijkstra merupakan salah satu algoritma yang digunakan untuk memecahkan
permasalahan lintasan terpendek yang terdapat pada suatu graf . Algoritma ini
digunakan pada graf berbobot dengan syarat bobot dari masing-masing sisi
haruslah bernilai positif (>=0). Dan dalam paper ini kita kan menyelesaikan
sustu masalah tentang pemilihan jalur tercepat dan efisien dari titik A ke
titik B dengan syarat harus melalui titik C dahulu sebelum ke titik B (tujuan)
B.
PENDAHULUAN
Permasalahan
optimasi merupakan permasalahan yang sering sekali kita temui dalam kehidupan sehari-hari.
Hal ini tidak lepas dari sifat dasar manusia yang selalu ingin mendapat
keuntungan semaksimum mungkin dan memperoleh kerugian seminimum mungkin. Jika
kita membicarakan permasalahan mengenai rute atau jalur yang menghubungkan
tempat-tempat tertentu maka kita sering menggambarkanya dengan bulatan untuk
memvisualisasikan tempat dan garis untuk jalan / rute. Representasi semacam ini
merupakan suatu representasi dari graf.
Graf
adalah himpunan simpul yang dihubungkan dengan suatu garis dimana garis tersebut
menghubungkan dengan tepat ke 2 simpul sehingga simpul-simpul ini saling
berhubungan. Dalam kehidupan sehari-hari banyak sekali persoalan yang di
implementasikan dengan graf. Bidang-bidang yang menggunakan penerapan graf
antara lain Switching network, Coding theory, Electrical analysis, Operation
research, aljabar, computer science, dan kimia.
Banyak
sekali aplikasi yang mengunakan graf sebagai alat untuk merepresentasikan atau
memodelkan persoalan sehingga persoalan itu dapat diselesaikan dengan baik.
Aplikasi - aplikasi tersebut misalnya menentukan lintasan terpendek (the
shortest path problem), traveling salesman problem, chinese postman problem,
graf colouring, Making a road system one-way, rangking the participants in a
tournament, dan masih banyak lagi. Dalam kesempatan ini kami mencoba mengulas
tentang persoalan menentukan lintasan terpendek (The Shortest Path Problem).
Aplikasi
yang paling sering ditemui adalah pada bidang transportasi, seperti pada
pencarian rute terbaik untuk menempuh dua kota. Dan di paper ini kita akan menyelesaikan
sebuah problem untuk menempuh jarak dari kota A ke kota B dengan menggunakan
Algoritma Djikstra. Semoga paper ini bisa bermanfaat bagi penulis dan pembaca.
C.
Dasar Teori
Dasar
teori yang digunakan dalam penyelesaian masalah pada paper ini dengan
menggunakan Algoritma djikstra, yaitu mencari rute permaslahan terpendek antara
simpul sumber menuju simpul tujuan
D.
Penjelasan Algoritma dan Uraian
Pemecahan Masalah
Untuk mencari rute terpendek, dapat
menggunakan beberapa metode, antara lain dengan menggunakan algoritma Dijkstra,
algoritma Bellman-ford, dan algoritma Warshall. Kali ini penulis akan
menyelesaikan suatu kasus dengan menggunakan Algoritma Djikstra.
Algoritma Dijkstra adalah suatu
algoritma rakus dimana algoritma ini digunakan untuk mencari rute permasalahan
terpendek antara simpul sumber dan simpul tujuan untuk sebuah graf berarah
berdasarkan bobot pada sisi yang bernilai tidak negatif. Algoritma Dijkstra
bekerja dengan cara mengunjungi simpul-simpul yang ada, dimulai dari simpul
sumber. Kemudian algoritma ini memilih simpul-simpul yang lokasinya terdekat
dan dilakukan secara berulang lalu kemudia menghitung total bobot semua sisi
yang dilewati untuk mencapai simpul tujuan.
Pada
algoritma dijkstra total biaya untuk mencapai suatu simpul adalah seperti ini :
(ni) = g(n) + c(n,ni)
(1)
Algoritma Dijkstra dijamin dapat
menemukan rute terpendek asalkan tidak terdapat bobot negatif pada setiap sisi
dalam graph [10]. Input untuk algoritma ini adalah sebuah graph yang berarah
dan berbobot G. Dan sebuah sumber vertex s dalam G. Dan V
merupakan himpunan semua vertice dalam grapf G. Setiap sisi
dari graph ini adalah pasangan vertice (u,v) yang melambangkan
hubungan vertex u dengan vertex v dan himpunan semua tepi E.
w : E [0, ∞) (2)
jadi w(u, v)
merupakan jarak non-negatif dari vertex u ke vertex v. Biaya
sebuah sisi dapat dianggap sebagai jarak antara dua buah vertex dan merupakan
jumplah jarak tiap sisi dalam jalur tersebut.
Gambar : Ilustrasi Algoritma Dijkstra
Contoh,
algoritma ini digunakan untuk menghitung jarak dari s ke t dalam V.
1. Function
Dijkstra
(G, w, s)
2. For
each vertex v in V[G]
3. d[V]
:= infinity
4. previous[v]
:= undefined
5. d[s]
:= 0
6. S
:= empty set
7. Q
:= V[G]
8. while
Q
is not an empty set
9. u
:= Extract_Min(Q)
10. S
:= S union {u}
11. For
each edge (u,v) outgoing from u
12. If
d[u]
+ w(u,v) < d[v]
13. d[v]
:= d[u] + w(u,v)
14. previous[v]
:= u
Pada baris kedua merupakan proses
inisialisasi, pada baris ke lima merupakan jarak dari s ke s. Baris ke tujuh
merupakan kumpulan dari semua vertice, dan baris kedelapan dan seterusnya
merupakan algoritmanya itu sendiri. Terdapat Pseudocode lain tentang Algoritma
Djikstra.
1. DIJKSTRA(G,
s, w)
2. for
each
vertex u in V
3. d[u]
:= infinity
4. p[u]
:= u
5. color[u]
:= WHITE
6. end
for
7. color[s]
:= GRAY
8. d[s]
:= 0
9. INSERT(Q,
s)
10. while
(Q
!= Ø)
11. u
:= EXTRACT-MIN(Q)
12. S
:= S U { u }
13. for
each
vertex v in Adj[u]
14. if
(w(u,v)
+ d[u] < d[v])
15. d[v]
:= w(u,v) + d[u]
16. p[v]
:= u
17. if
(color[v]
= WHITE)
18. color[v]
:= GRAY
19. INSERT(Q,
v)
20. else
if (color[v]
= GRAY)
21. DECREASE-KEY(Q,
v)
22. Else
23. ...
24. end
for
25. color[u]
:= BLACK
26. end
while
27. return
(d, p)
Pada baris ke-9
dilakukan pencarian vertex s, lalu pada baris ke 11, dilakukan
pengecekan terhadap vertex u. Kemudian pada baris 13, dilakukan
pengecekanpinggiran/ujung (u,v). Lalu pada baris ke-19 dilakukan
pencarian vertex v. Dan pada baris ke-24, menyelesaikan vertex u.
Gambar
: Ilustrasi kelemahan algoritma dijkstra.
Waktu yang dibutuhkan
oleh algoritma dijkstra adalah O(|V|2). Waktu ini dapat dikurangi menjadi
O(|E|log|V|) apabila heap digunakan untuk menjaga {v in V\Si : L(v) <
infinity}.
Menurut
teori graf, persoalan lintasan terpendek adalah suatu persoalan untuk mencari
lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai
jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum.
Persoalan
lintasan terpendek merupakan salah satu persoalan optimasi yeng menggunakan
graf berbobot, dimana bobot pada setiap sisi graf tersebut dapat kita gunakan
untuk menyatakan jarak kota, waktu pengiriman pesan, ongkos pembangunan, dan
sebagainya.
Coba
perhatikan contoh pemecahan masalah dengan algoritma djikstra di bawah ini.
Pertama-tama tentukan titik mana yang akan menjadi node awal, lalu beri
bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan
melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik
selanjutnya tahap demi tahap. Inilah urutan logika dari algoritma Dijkstra:
1.
Beri
nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada
node awal dan nilai tak hingga terhadap node lain (belum terisi)
2.
Set
semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”
3.
Dari
node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung
jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A
ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C
melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak sebelumnya
(yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan
jarak yang baru.
4.
Saat
kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node
yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di
cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal
bobotnya.
5.
Set
“Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai
“Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.
E.
Proses
Seperti
yang telah kita bahas sebelumnya bahwa kita akan menyelesaikan masalah
menggunakan metode Algoritma Djikstra yang memilih rute yang paling pendek dari
titik awal ke titik tujuan (Vertex sumber ke Vertex tujuan).
Perhatikan
gambar di bawah ini. Gambar di bawah ini yang akan kita selesaikan dengan
Algoritma Djikstra. Mula-mula kita berada pada V1 lalu kita memilih
jalur terccepat dan terdekat agar biasa sampai ke titik V11, tetapi
harus melewati titik V6 terlebih dahulu sebelum sampai ke titik V11
dengan cepat dibandingkan melewati titik lain yang jauh. Umpamakan nilai-nilai
edge tersebut bersatuan km.
1. Langkah
yang pertama yaitu mrmilih jalur dari titik V1 yang paling pendek,
ternyata di gambar itu ada yang paling dekat jaraknya yaitu titik V4,
hanya berjarak 1km. dan jarak terdekat kedua yaitu titik V2 yang
berjarak 2 km. dan yang paling jauh yaitu titik V3 yang sejauh 8 km.
2. Pilihlah
titik yang paling dekat dengan V4. Dari V4 ke titik selanjutnya
menempuh jarak 9 km, jadi totalnya 10 km (1+9). tapi lihat perbandingannya
dengan titik V3 ke titik V6, hanya 1 km, totalnya 9 km
(8+1). Dan lihat titik V2 menuju titik V5 hanya 1 km, dan
totalnya 3 km (2+1). Maka kita bissa menghapus kesimpulan pertama tadi dan mengganti
kesimpulan kita menjadi V1 (0 km) – V2 (2 km) – V5
(1 km) – V6 (3 km) – V9 (6 km) – V11 (2 km).
3. Sampailah
di titik V11 denan melewati titik V6 terlebih dahulu,
dengan total jarak 14 km.
F.
Kesimpulan
Jadi,
rute terdekat yang harus di tempuh dari titik V1 menuju titik V11
dengan melewati titik V6 terlebih dahulu yaitu V1 (0 km)
– V2 (2 km) – V5 (1 km) – V6 (3 km) – V9
(6 km) – V11 (2 km) yang total jaraknya sejauh 14 km, lebih dekat
dibandingkan rute yang lainnya.
G.
Daftar Referensi
Tidak ada komentar:
Posting Komentar