Pengukuran jarak dalam GIS (Bagian 4)

4. Metode A*

Algoritma ini pertama kali diperkenalkan pada 1968 oleh Peter Hart, Nils Nilsson, dan Bertram Raphael. Dalam ilmu komputer, A* (yang disebut dengan “A star”) merupakan salah satu algoritma pencarian graph terbaik yang mampu menemukan jalur dengan biaya pengeluaran paling sedikit dari titik awal yang diberikan sampai ke titik tujuan yang diharapkan (dari satu atau lebih tujuan).

Algoritma A* (Admissible Heuristic) adalah strategi best first search yang menggunakan estimasi solusi biaya terkecil untuk mencapai suatu tujuan dengan jarak tempuh terdekat dan memiliki nilai heuristik yang digunakan sebagai dasar pertimbangan. Heuristik adalah kriteria, metode, atau prinsip-prinsip untuk menentukan pilihan sejumlah alternatif untuk mencapai sasaran dengan efektif.

Nilai heuristik dipergunakan untuk mempersempit ruang pencarian. Metode pencarian A* menghasilkan jalur optimal mulai dari tempat awal kemudian melalui graph menuju tempat yang dituju. Metode ini berdasarkan formula :

f(n) = g(n)+h(n)

Keterangan :

h(n) = biaya estimasi dari node n ke tujuan

g(n) = baya path atau perjalanan

f(n) = solusi biaya estimasi termurah node n untuk mencapai tujuan.

Gambar. Metode A*

langkah perhitungan Metode A*

Algoritma A* secara garis besar dapat dijelaskan seperti berikut:

1. Masukkan node awal ke openlist

2. Loop langkah-langkah dibawah ini:

    a. Cari node (n) dengan nilai f(n) yang paling kecil dalam open list, dan node ini sekarang menjadi current node.

    b. Keluarkan current node dari openlist dan masukkan ke open list

    c. Untuk setiap tetangga dari current node lakukan berikut

        1. Jika tidak dapat dilalui atau sudah ada dalam close list , abaikan

       2. Jika belum ada di open list buat current node parent dari node tetangga ini, simpan nilai f,g, dan h dari node ini.

       3. Jika sudah ada di openlist cek apabila node tetangga ini lebih baik menggunakan nilai g sebagai ukuran. Jika lebih baik ganti parent dari node ini di opentlist menjadi current node, lalu kalkulasikan ulang nilai g dan f dari node ini.

     d. Hentikan looping jika:

         1. Node tujuan telah ditambah ke openlist yang berarti rute ditemukan

         2. Belum menemukan node akhir (tujuan) sementara openlist kosong atau berarti tidak ada rute.

Simpan rute, lalu secara backward urut mulai dari node akhir (tujuan) sampai ke titik awal sambil menyimpan node ke dalam array.

berikut ini contoh perhitungan metode A* menurut Yulani, dan Fahrul Agus:

Gambar. peta contoh perhitungan

Keterangan :

Length = Panjang jarak antara titik awal dan titik akhir

Titik Awal = Dinas Kesehatan

Titik Akhir = Dinas Kebersihan, Pertamanan, dan Pemadam Kebakaran

Cara perhitungan yang dipakai dalam pencarian rute :

F(n) = g(n) + h(n)

Keterangan :

F(n) = Jumlah dari g(n) + h(n), perkiraan jalur terpendek sementara

g(n) = Total jarak yang di dapat dari vertex awal ke vertex akhir

h(n) = Perkiraan jarak dari vertex sekarang yang sedang dikunjungi ke vertex tujuan

1. Jarak 2 node :

N[1][2] = (√ ( (X2 – X1)2 + (Y2-Y1)2 ) )

Langkah 1 :

N[0][123]

g = N[0][123] = 25

N[123][122] :

g = N[123][122] = N[0][123] + N[123][122] = 25 + 79 = 104

h = N[122][86] = (√ ( (117 – 89)2+ (119 – 90)2) ) = 40

f = g + h = 144

Karena hanya ada 1 koneksi maka dipilih N[123][122]

Langkah 2 :

N[122][121] :

g = N[0][123] + N[123][122] + N[122][121] = 25 + 79 + 195 = 299

h = N[121][86] = 39

f = g + h = 338

N[122][116] :

g = N[0][123] + N[123][122] + N[122][116] = 25 + 79 + 136 = 240

h = N[116][86] = 38

f = g + h = 278

Dipilih N[122][116]

Langkah 3 :

N[122][121] : g = 299, h = 39, f = 338

N[116][118] :

g = N[0][123] + N[123][122] + N[122][116] + [116][118] = 25 + 79 + 136 + 942 = 1182

h = N[118][86] = 25

f = g + h = 1233

Dipilh N[122][121]

Langkah 4 :

N[116][118] : g = 1182, h = 25 ,f = 1233

N[121][3] :

g = N[0][123] + N[123][122] + N[122][121] + [121][3] = 25 + 79 + 195 + 508 = 806

h = N[3][86] = 36

f = g + h = 842

N[121][1] :

g = N[0][123] + N[123][122] + N[122][121] + [121][1] = 25 + 79 + 195 + 950 = 1249

h = N[1][86] = 26

f = g + h = 1305

Dipilih N [121][3]

Langkah 5 :

N[116][118] : g = 1182, h = 25 ,f = 1233

N[121][1] : g = 1249, h = 26 ,f = 1305

N[3][67] :

g = N[0][123] + N[123][122] + N[122][121] + [121][3] + [3][67] = 25 + 79 + 195 + 508 + 168 = 975

h = N[67][86] = 26

f = g + h = 1001

Dipilih N [3][67]

Langkah 6 :

N[116][118] : g = 1182, h = 25 ,f = 1233

N[121][1] : g = 1249, h = 26 ,f = 1305

N[67][70] :

g = N[0][123] + N[123][122] + N[122][121] + [121][3] + [3][67] + [67][70] = 25 + 79 + 195 + 508 + 168 + 90 = 1065

h = N[70][86] = 16

f = g + h = 1081

Dipilih N [67][70]

Langkah 7 :

N[116][118] : g = 1182, h = 25 ,f = 1233

N[121][1] : g = 1249, h = 26 ,f = 1305

N[70][69] :

g = N[0][123] + N[123][122] + N[122][121] + [121][3] + [3][67] + [67][70] + [70][69] = 25 + 79 + 195 + 508 + 168 + 90 + 62 = 1127

h = N[69][86] = 5

f = g + h = 1132

Dipilih N [70][69]

Langkah 8 :

N[116][118] : g = 1182, h = 25 ,f = 1233

N[121][1] : g = 1249, h = 26 ,f = 1305

N[69][1] :

g = N[0][123] + N[123][122] + N[122][121] + [121][3] + [3][67] + [67][70] + [70][69] + [69][1] = 25 + 79 + 195 + 508 + 168 + 90 + 62 + 546 = 1673

h = N[1][86] = 26

f = g + h = 1699

Dipilih N [116][118]

Langkah 9 :

N[121][1] : g = 1249, h = 26 ,f = 1305

N[69][1] : g = 1673, h = 26, f = 1699

N[118][119] :

g = N[0][123] + N[123][122] + N[122][116] + N[116][118] + N[118][119] = 25 + 79 + 136 + 942 + 117 = 1299

h = N[119][86] = 4

f = g + h = 1303

Dipilih N [118][119]

Langkah 10 :

N[121][1] : g = 1249, h = 26 ,f = 1305

N[69][1] : g = 1673, h = 26, f = 1699

N[119][1] :

g = N[0][123] + N[123][122] + N[122][116] + N[116][118] + N[118][119] + [119][1] = 25 + 79 + 136 + 942 + 117 + 198 = 1497

h = N[1][86] = 26

f = g + h = 1523

Dipilih N [121][1]

Langkah 11 :

N[69][1] : g = 1673, h = 26, f = 1699

N[119][1] : g = 1497, h = 26, f = 1523

N[1][86] :

g = N[0][123] + N[123][122] + N[122][121] + N[121][1] + [1][86] = 25 + 79 + 195 + 950 + 493 = 1742

h = N[86][86] = 0

f = g + h = 1742

Dipilih N[1][86].

Pencarian rute terpendek berhenti karena sudah sampai node tujuan. Rute yang didapat adalah : 0–123–122–121–1–86 yaitu Titik awal>DK[123] > Jln.Jend Ahmad yani[122] > Jln.Jend Ahmad Yani[121] > Jln.Jend DI Panjaitan[1] > Jln.Kapt Piere Tendean[86].

Dibawah ini akan diperlihatkan tampilan keluaran dari sistem ketika dilakukan pencarian dengan titik awal dan titik akhir yang sama.

Gambar. Hasil perhitungan A*

itulah sedikit penjelasan dari metode A*, semoga dapat membantu.

untuk pembahasan pengukuran jarak suatu tempat dengan GIS penulis jadikan empat bagian, karena pembahasannya yang panjang. jadi agar lebih efisien penulis pecah menjadi empat pembahasan.

sumber:

Yuliani, Agus, Fahrul. (2013),  Webgis Pencarian Rute Terpendek Menggunakan Algoritm A Star (A*)

Pengukuran jarak dalam GIS (Bagian 3)

3. Metode ant colony.

Koloni semut merupakan algorima yang bersifat heuristik untuk menyelesaikan masalah optimasi. Algoritma ini diinspirasikan oleh lingkungan kooni semut pada saat mencari makanan. Semut dapat mencari makanan. Semut dapat mencari lintasan terpendek dari suatu sumber makanan menuju sarangnya, tanpa harus melihatnya secara langsung. Karena terinspirasi dari semut asli dinamakan algoritma koloni semut. Semut-semut mempunyai penyelesaian yang unik dan sangat maju, yaitu menggunakan jejak pheromone pada suatu jalur untuk berkomunikasi dan membangun solusi, semakin banyak jejak pheromone ditinggalkan, maka jalur tersebut akan diikuti oleh semut lain.

Gambar. Metode ant colony.

menurut Yuwono, Sasmito, Aribowo, dan Wardoyo (2009), dalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah untuk menentukan jalur

terpendek, yaitu:

- Langkah 1 :

   a. Inisialisasi harga parameter-parameter algoritma. Parameter-parameter yang di inisialisasikan               adalah :

         1. Intensitas jejak semut antar kota dan perubahannya ( ij)

         2. Banyak kota (n) termasuk x dan y (koordinat) atau dij (jarak antar kota)

         3. Penentuan kota berangkat dan kota tujuan

         4. Tetapan siklus-semut (Q)

         5. Tetapan pengendali intensitas jejak semut ( )

         6. Tetapan pengendali visibilitas ( )

         7. Visibilitas antar kota = 1/dij ( ij)

         8. Jumlah semut (m)

         9. Tetapan penguapan jejak semut ( )

       10. jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan ij

             akan selalu diperbaharui harganya pada setiap siklus algoritma mulai dari siklus pertama

             (NC=1) sampai tercapai jumlah siklus maksimum (NC=NCmax) atau sampai terjadi 

             konvergensi.

      b. Inisialisasi kota pertama setiap semut. Setelah inisialisasi ij dilakukan, kemudian m semut                ditempatkan pada kota pertama yang telah ditentukan.

- Langkah 2 :

Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama semut pada langkah 1 harus

diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks kota pertama.

- Langkah 3 :

Penyusunan jalur kunjungan setiap semut ke setiap kota. Koloni semut yang sudah terdistribusi ke kota pertama akan mulai melakukan perjalanan dari kota pertama sebagai kota asal dan salah satu kota-kota lainnya sebagai kota tujuan. Kemudian dari kota kedua, masing-masing koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada tabuk sebagai kota tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus hingga mencapai kota yang telah ditentukan. Jika s menyatakan indeks urutan kunjungan, kota asal dinyatakan sebagai tabuk(s) dan kota-kota lainnya dinyatakan sebagai {N-tabuk}, maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut,

p k/ij = 0, untuk j lainnya dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan.

- Langkah 4 :

  a. Perhitungan panjang jalur setiap semut.

      Perhitungan panjang jalur tertutup (length closed tour) atau Lk setiap semut dilakukan setelah

      satu siklus diselesaikan oleh semua semut. Perhitungan dilakukan berdasarkan tabuk masing-              masing dengan persamaan berikut:

      dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan:

b. Pencarian rute terpendek.

    Setelah Lk setiap semut dihitung, akan diperoleh harga minimal panjang jalur tertutup setiap

    siklus atau LminNC dan harga minimal panjang jalur tertutup secara keseluruhan adalah atau Lmin.

c. Perhitungan perubahan harga intensitas jejak kaki semut antar kota.

    Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan antar kota yang dilaluinya. Adanya

    penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya                perubahan harga intensitas jejak kaki semut antar kota. Persamaan perubahannya adalah:

   dengan k ij adalah perubahan harga intensitas jejak kaki semut antar kota setiap semut yang           dihitung berdasarkan persamaan

untuk (i,j)  kota asal dan kota tujuan dalam tabuk

k/ij = 0, untuk (i,j) lainnya

- Langkah 5 :

   a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya.

      Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan              berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus              selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga        intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung dengan persamaan :

b. Atur ulang harga perubahan intensitas jejak kaki semut antar kota.

    Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur kembali          agar memiliki nilai sama dengan nol.

- Langkah 6 :

  Pengosongan tabu list, dan ulangi langkah dua jika diperlukan. Tabu list perlu dikosongkan untuk        diisi lagi dengan urutan kota yang baru pada siklus selanjutnya, jika jumlah siklus maksimum 

  belum tercapai atau belum terjadi konvergensi. Algoritma diulang lagi dari langkah dua dengan          harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui.

itulah sedikit penjelasan dari metode ant colony. semoga dapat membantu.

sumber:

Yuwono, Sasmito, Aribowo, dan Wardoyo. (2009), Implementasi Algoritma Koloni Semut Pada Proses Pencarian Jalur Terpendek Jalan Protokol Di Kota Yogyakarta, seminar nasional informatika 2009 (semnasIF 2009),  hal A-111-A-120.

Pengukuran jarak dalam GIS (Bagian 2)

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.