Salah satu persoalan optimasi yang sering ditemui dalam kehidupan sehari-hari adalah pencarian lintasan terpendek (shortest path). Persoalan ini bisa dimodelkan ke dalam suatu graf berbobot dengan nilai pada masing-masing sisi yang merepresentasikan persoalan yang akan dipecahkan.
Algoritma Dijkstra merupakan salah satu varian dari algoritma greedy, yaitu salah satu bentuk algoritma populer dalam pemecahan persoalan yang terkait dengan masalah optimasi. Sifatnya sederhana dan lempang (straightforward).
Dalam pengimplementasiannya dalam program aplikasi On Taxi yang kami buat, algoritma Djikstra digunakan untuk mencari lintasan terpendek dari titik awal ke titik tujuan yang terhubung oleh node-node yang telah ditentukan jaraknya pada peta. Masing-masing node pada peta telah ditentukan koordinatnya. Proses berawal dari penentuan titik awal dan titik akhir oleh user yang kemudian akan diproses. Misalkan titik awal pada node #1 dan titik akhir pada node#42, program mencari segala kemungkinan cabang/rute dari node awal ke node akhir menghasilkan rentetan node-node sebagai lintasan. Program akan menyimpan urutan node-node yang terbentuk dalam sebuah array sehingga menjadi suatu rentetan node / lintasan. Semua kemungkinan rentetan node akan dibandingkan dan dipilih rentetan mana yang memiliki jumlah node paling sedikit.
Rentetan node yang memiliki jumlah node paling sedikit merupakan lintasan yang menghubungkan node awal ke node akhir dengan jarak terpendek.
Filed under: Uncategorized Tagged: | Algoritma, aplikasi, Djikstra, JAVA
