2. Metode Dijkstra
Algoritma atau metode Dijkstra adalah suatu metode yang digunakan untuk menentukan jarak terpendek dari suatu tempat. metode dijkstra termasuk dalam metode greedy, karena setiap jalur akan diperiksa oleh metode ini. metode dijkstra diaplikasikan dalam satu sumber graf yang tidak memiliki cost sisi negatif dan menghasilkan pohon lintasan terpendek. Ide dasar algoritma Dijkstra sendiri ialah pencarian nilai costyang terdekat dengan tujuan yang berfungsi pada sebuah graf berbobot, sehingga dapat membantu memberikan pilihan jalur. Pada AlgoritmaDijkstra, node digunakan karena Algorima Dijkstra menggunakan graphberarah untuk penentuan rute lintasan terpendek. Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis menggambarkan jalan, maka Algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.
Gambar 1.3. node dijkstra
Berikut ini akan dijelaskan langkah-langkah perhitungan algoritma Dijkstra menurut Dwi Ardana dan Ragil Saputra:
Pertama-tama tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Algoritma Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap. Urutan logika dari Algoritma Dijkstra sebagai berikut:
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 (2016).
berikut ini dijelaskan contoh perhitungan dijkstra yang dikutip dari penelitian yang dilakukan oleh Amden Julianto J. M. dan Muh. Yamin (2015). Untuk mencari jarak terpendek, algoritma Dijkstra mempunyai sistem perhitungan seperti yang dijelaskan diatas, dan perhitungannya adalah sebagai berikut:
Langkah pertama yang harus dilakukan adalah dengan menentukan jarak dari titik satu ke ttik yang lainnya. Jarak setiap titik akan dijelaskan pada tabel 3.1 dibawah ini.
Tabel 1.1. jarak setiap titik
Setelah jarak setiap titik didapatkan, maka langkah selanjutnya adalah menggambarkan model graf seperti pada gambar dibawah ini
Gambar 1.4. Model Graf Algoritma Dijsktra
Berikut ini langkah-langkah dalam menentukan jarak terpendek menggunakan metode Dijkstra;
A. Langkah 1
- Menentukan node Awal (Pa) = S.
- Menentukan node Tujuan (Pt) = T.
B. Langkah 2
- Menetapkan node S (Pa) sebagai node permanen dan jarak = 0.
- Mengecek jalur yang dapat dilalui dari titik Pa.
- Terdapat 1 jalur yang dapat dilalui dari node S yaitu node A.
- Menghitung jarak dari node S (Pa) ke node A.
- Diketahui jarak node S ke node A = 39,76 m.
- Mengubah Node A menjadi T-node.
- Mengecek apakah T-node = Pt atau node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A.
C. Langkah 3
- Mengecek jalur yang dapat dilalui dari node S, A.
- Terdapat 2 jalur yang dapat dilalui dari node S, A yaitu node B dan node J.
- Menghitung jarak dari node S, A ke node B.
- Diketahui jarak node S, A ke Node B = 39,76 m + 66,62 m = 106,38 m.
- Menghitung jarak dari node S, A ke node J. Jarak node S, A ke node B lebih kecil daripada node S, A ke node J.
- Menjadikan node S, A, J sebagai jalur bercabang.
D. Langkah 4
- Mengecek jalur yang dapat dilalui dari node S, A, B.
- Terdapat 1 jalur yang dapat dilalui dari node S, A, B yaitu node C.
- Menghitung jarak dari node S, A, B ke node C.
- Diketahui jarak node S, A, B ke Node C = 106,38 m + 51,04 m = 157,42 m.
- Mengubah node C menjadi T-node.
- Mengcek apakah T-node = Pt atau Node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A, B, C.
- Mengubah node B menjadi T-node.
- Mengecek apakah T-node = Pt atau node T.
- T-node bukan Node T sehingga T-node berubah menjadi node S, A, B.
- Diketahui jarak node S,A ke node J = 39,76 m + 75,09 m = 114,45 m.
- Membandingkan jarak antara node S, A ke node B dengan node S, A ke node J.
- Membandingkan jalur terpendek antara Node S, A, B, C (157,42 m) dan Node S, A, J (114,45 m).
- Node S, A, J lebih pendek sehingga node ini yang digunakan.
E. Langkah 5
- Mengecek jalur yang bercabang yaitu node S, A, J.
- Terdapat 1 jalur yang dapat dilalui dari node S, A, J yaitu node K.
- Menghitung jarak dari node S, A, J ke node K.
- Diketahui jarak node S, A, J ke Node K = 114,45 m + 64,69 m = 179,14 m.
- Mengubah node K menjadi T-node.
- Mengecek apakah T-node = Pt atau Node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A, J, K.
- Membandingkan jalur terpendek antara node S, A, J, K (179,14 m) dan node S, A, B, C (157,42 m).
- Node S, A, B, C lebih pendek sehingga node ini yang digunakan.
F. Langkah 6
- Mengecek jalur yang dapat dilalui dari node S, A, B, C. Terdapat 1 jalur yang dapat dilalui dari node S, A, B, C yaitu node D.
- Menghitung jarak dari node S, A, B, C ke node D.
- Diketahui jarak node S, A, B, C ke Node D = 157,42 m + 25,39 m = 182,81 m.
- Mengubah node D menjadi T-node.
- Mengecek apakah T-node = Pt atau Node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A, B, C, D.
- Membandingkan jalur terpendek antara node S, A, J, K (179,14 m) dan node S, A, B, C ,D (182,81 m).
- Node S, A, J, K lebih pendek sehingga node ini yang digunakan.
G. Langkah 7
- Mengecek jalur yang dapat dilalui dari node S, A, J, K.
- Terdapat 1 jalur yang dapat dilalui dari node S, A, J, K yaitu node L.
- Menghitung jarak dari node S, A, J, K ke node L.
- Diketahui jarak node S, A, J, K ke node L = 179,14 m + 270,79 m = 449,93m.
- Mengubah node L menjadi T-node.
- Mengecek apakah T-node = Pt atau node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A, J, K, L.
- Membandingkan jalur terpendek antara node S, A, J, K, L (449,93 m) dan node S, A, B, C ,D (182,81 m).
- Node S, A, B, C ,D lebih pendek sehingga node ini yang digunakan.
H. Langkah 8
- Mengecek jalur yang dapat dilalui dari node S, A, B, C ,D. Terdapat 1 jalur yang dapat dilalui dari node S, A, B, C, D yaitu node E.
- Menghitung jarak dari node S, A, B, C, D ke node E.
- Diketahui jarak node S, A, B, C, D ke Node E = 182,81 m + 176,57 m = 359,38 m.
- Ubah node E menjadi T-node.
- Mengecek apakah T-node = Pt atau node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A, B, C, D, E.
- Membandingkan jalur terpendek antara node S, A, J, K, L (449,93 m) dan node S, A, B, C ,D,E (359,38 m).
- Node S, A, B, C, D, E lebih pendek sehingga node ini yang digunakan.
I. Langkah 9
- Mengecek jalur yang dapat dilalui dari node S, A, B, C, D, E.
- Terdapat 1 jalur yang dapat dilalui dari node S, A, B, C, D, E yaitu node F.
- Menghitung jarak dari node S, A, B, C, D, E ke node F.
- Diketahui jarak node S, A, B, C, D, E ke node F = 359,38 m + 10,30 m = 369,68 m.
- Mengubah node F menjadi T-node.
- Mengecek apakah T-node = Pt atau node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A, B, C, D, E, F.
- Membandingkan jalur terpendek antara node S, A, J, K, L (449,93 m) dan node S, A, B, C, D, E, F (369,68 m).
- Node S, A, B, C, D, E, F lebih pendek sehingga node ini yang digunakan.
J. Langkah 10
- Mengecek jalur yang dapat dilalui dari node S, A, B, C, D, E, F.
- Terdapat 1 jalur yang dapat dilalui dari node S, A, B, C, D, E, F yaitu node G.
- Menghitung jarak dari node S, A, B, C, D, E, F ke node G.
- Diketahui jarak node S, A, B, C, D, E, F ke node G = 369,68 m + 23,78 m = 393,46 m.
- Mengubah node G menjadi T-node.
- Mengecek apakah T-node = Pt atau node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A, B, C, D, E, F, G.
- Membandingkan jalur terpendek antara node S, A, J, K, L (449,93 m) dan node S, A, B, C, D, E, F, G (393,46 m).
- Node S, A, B, C, D, E, F, G lebih pendek sehingga node ini yang digunakan.
K. Langkah 11
- Mengecek jalur yang dapat dilalui dari node S, A, B, C, D, E, F, G.
- Terdapat 2 jalur yang dapat dilalui dari node S, A, B, C, D, E, F, G yaitu node I dan node N.
- Jarak node S, A, B, C, D, E, F, G ke node I lebih kecil daripada node S, A, B, C, D, E, F, G ke node N.
- Mengubah node I menjadi T-node.
- Mengecek apakah T-node = Pt atau node T.
- T-node bukan node T sehingga T-node berubah menjadi node S, A, B, C, D, E, F, G, I.
- Membandingkan jalur terpendek antara node S, A, J, K, L (449,93 m) dan node S, A, B, C, D, E, F, G, I (405,94 m).
- Node S, A, B, C, D, E, F, G, I lebih pendek sehingga node ini yang digunakan.
L. Langkah 12
- Mengecek jalur yang dapat dilalui dari node S, A, B, C, D, E, F, G, I.
- Terdapat 1 jalur yang dapat dilalui dari node S, A, B, C, D, E, F, G, I yaitu node T.
- Menghitung jarak dari node S, A, B, C, D, E, F, G, I ke node T.
- Diketahui jarak node S, A, B, C, D, E, F, G, I ke Node T = 405,94 m + 54,42 m = 460,36 m.
- Mengubah node T menjadi T-node.
- Mengecek apakah T-node = Pt atau node T.
- T-node adalah node T sehingga jalur terpendek yang tercipta untuk mencapai tujuan adalah node S, A, B, C, D, E, F, G, I, T.
Hasil akhir dari perhitungan jarak terpendek menggunakan algoritma Dijkstra berdasarkan langkah perhitungan diatas adalah seperti ditunjukkan oleh gambar dibawah ini:
Gambar 1.5. hasil perhitungan metode Dijkstra
itulah penjelasan singkat yang dapat penulis sampaikan tentang metode dijkstra. semoga bisa bermanfaat bagi pembaca. dan pada kesempatan berikutnya penulis akan menjelaskan tentang agoritma Ant Colony dan A*.
sumber:
1. Ardana, Dwi. & Saputra, Ragil. (2016). Penerapan Algoritma Dijkstra pada Aplikasi Pencarian Rute Bus Trans Semarang, Seminar Nasional Ilmu Komputer (SNIK 2016), Semarang, hal. 299-306.
2. Marseno, Amden Junianto Jalu , Yamin, Muh. (2015). Panduan Pencarian Rute Gedung Dan Ruangan Pada Fakultas Di Universitas Halu Oleo Menggunakan Algoritma Dijkstra Berbasis Macromedia Flash, semanTIK, Vol.1, No.2, hal. 45-56.
Tidak ada komentar:
Posting Komentar