Algoritma Dijkstra Dasar, Tak Semudah Kubayangkan Waks

Saya kadang terheran-heran alias wondering gimana caranya Google Maps nentuin rute terbaik pas kita cari tujuan.

Mungkin saya paham Google mengutamakan jalanan besar dahulu baru jalan-jalan tikusnya. Terus prioritas lainnya mungkin kondisi trafik macet atau nggaknya, dst.

Nah, ada algoritma buat ngehandle ini, setahu saya ada dua, Dijkstra dan A* (A star).

Sebenernya dua-duanya sama aja. Cuma bedanya, Dijkstra yang saya tangkep mungkin lebih ke brute-force alias selama masih ada jalan hajar aja semua sampe ketemu tujuan.

Sedangkan A* lebih heuristik atau apalah itu sebutannya, yang maksudnya lebih mengutamakan nyambungin poin atau jalan-jalan yang lebih deket ke tujuan daripada brute-force.

Misalnya, saya dari Jakarta mau ke Majalengka.

Majalengka itu ada di sebelah timur Jakarta.

Kalau pakai Dijkstra, seluruh 8 arah mata angin dari Jakarta disambung semuanya sampe ketemu Majalengka.

Tapi kalau pakai Astar, lebih diutamain buat cari jalan yang lebih timur Jakarta dulu daripada arah lainnya. Dijkstra juga bisa begini sih, tapi secara gamblang begitulah perbedaan kedua algonya.

Algoritma Dijkstra Paling Dasar

Konon katanya, algo Dijkstra lebih gampang daripada A*, maka dari itu saya mau coba-coba bikin dengan mangsa peta stasiun KRL Jabodetabek.

Algonya kira-kira begini:

1. Bikin array yang isinya seluruh stasiun, bilang aja kumpulan stasiun yang belum kecolak-colek sama algonya. Lalu bikin array kosongan yang nantinya setiap stasiun yang udah tersentuh algo Dijkstra ini dimasukin di sini.

2. Tentuin stasiun mulai dan stasiun tujuan. Masukin stasiun mulai ke array yang udah tersentuh algonya.

3. Cari tetangga masing-masing stasiun. Cari semuanya termasuk di stasiun transit atau di stasiun ekstensi kayak Cibinong dan Nambo yang ekstensi dari jalur Bogor.

4. Seluruh tetangga yang kita dapet masukin ke array yang tersentuh algo. Masukin juga stasiun sebelumnya sebagai bagian dari data stasiun.

5. Ulangi langkah ke-tiga, tapi dengan syarat, stasiun tetangga tidak boleh sama dengan yang sudah ada di array yang tersentuh algo.

6. Kalau stasiunnya sudah ketemu atau ternyata sudah tidak ada lagi tetangga yang tersedia (alias tujuan tidak ketemu meski udah dicari seluruh stasiun), algoritma sudah selesai.

Untuk permulaan, kita belum menghitung jarak antar stasiun di sini. Hanya brute-force. Untuk skala kecil atau sekadar pembelajaran, tidak masalah karena tujuan utamanya cuma sampe ke stasiun yang ingin kita tuju aja.

Mungkin di artikel lain yang bakal saya beri judul Dijkstra Lanjutan akan saya buat lebih efisien.

Drama Penerapan Algo

Bagi saya yang pertama kali coba algo Dijkstra ini justru punya kendala besar tentang struktur arraynya.

Contohnya, di Javascript, saya nggak tau gimana isi dari array yang sudah tersentuh algo itu strukturnya gimana.

Karenanya, algoritma Dijkstra ini wajib tempelin stasiun sebelumnya di stasiun yang akan masuk ke array yang tersentuh algo.

Dari data stasiun sebelumnya inilah, saat algonya selesai dan stasiun tujuan ditemukan, rute perjalanannya disambung-sambung dari data stasiun sebelumnya sampai dapet stasiun awal.

Di Javascript, saya masukin data stasiun sebelumnya, termasuk jalur, dan jaraknya di object. Jadi array yang sudah tersentuh algo ini isinya kumpulan object stasiun.

Data jalur dan jarak saya ambil dari peta resmi PT. Kereta Commuter Indonesia. Cuma untuk sekarang di tahap dasar ini, variabel jarak stasiun masih belum ada pengaruhnya sama sekali kecuali untuk sekadar memberikan info saja.

Beberapa masih buggy, seperti yang dari Stasiun Tebet ke Jakarta Kota, ini algo lebih milih yang transit dan muter-muter padahal bisa tinggal lurus dan tanpa transit.

Itu karena algonya masih mentah, belum kenal sistem transit dan jarak, cuma baru bisa milih rute berdasarkan jumlah stasiun paling sedikit aja.

Berikut interaktifnya.

Pengembangan Ke Depan

Saya punya rencana ngembangin algo Dijkstra ini supaya lebih efisien. Poin-poin yang dapat saya kembangin adalah:

1. Bisa lebih milih rute efisien, misalnya yang tanpa transit kalau memungkinkan.
2. Bisa memuat rute alternatif, yang sekarang begitu ketemu tujuannya langsung saya stop.

Ya begitu lah, gak semudah yang saya pikir, terutama bangun array untuk rutenya. Tapi kalau dikhususkan untuk dasar, algoritma Dijkstra ini memang seperti ini adanya.