Algoritma adalah urutan atau langkah-langkah untuk penghitungan atau untuk menyelesaikan suatu masalah yang ditulis secara berurutan. Sehingga, algoritma pemrograman adalah urutan atau langkah-langkah untuk menyelesaikan masalah pemrograman komputer.
Saat ini siapa yang tidak mengenal kecanggihan salah satu fitur google yaitu google maps. Di era yang semakin canggih ini bepergian kemanapun tujuan kita tidak akan menjadi masalah selama bisa mengakses layanan google maps yang memudahkan dalam pencarian rute terbaik dan terpendek untuk menuju ke tempat yang diinginkan.
Pertanyaannya algoritma seperti apa yang diterapkan pada google maps? Google maps menggunakan algoritma dijkstra untuk menentukan rute yang paling efisien. Algoritma dijkstra sendiri adalah sebuah algoritma yang dipakai untuk memecahkan permasalahan jarak terpendek(shortest path problem) untuk sebuah graf berarah directed graph) dengan cara memeriksa dan membandingkan setiap jalur yang ada.
Google maps melihat suatu peta sebagai grafik yang terdiri dari nodus nodus lokasi dan tepian jalan yang menghubungkan lokasi yang berbeda. Ketika kita ingin pergi dari tempat A ke tempat Z google akan membacanya sebagai titik A ke titik Z, algortma dijkstra bekerja dengan menghubungkan simpul simpul yang ada di setiap tepi dan mencari jarak terpendek untuk sampai ditempat tujuan. Namun, dijkstra tidak hanya bekerja menentukan jarak yang mana belum tentu merupakan rute yang paling efisien, bisa jadi dirute tersebut terjadi kemacetan atau hal lainnya sehingga, dijkstra juga menggunakan parameter seperti : Panjang jalan, Jumlah jalur, Lampu lalu lintas, Data lalu lintas (real time / perkiraan) Untuk menentukan rute paling efisien.
Sumber :
Mencari sebuah tempat atau menentukan rute jalan terpendek di gadget sekarang bukan lagi sebuah hal yang sulit. Google Map salah satu solusinya, dimana fitur-fitur yang memanfaatkan fungsi navigasi peta begitu hidup di sana. Teknologi GPS mengakomodir penentuan posisi device, sedangkan implementasi network analyst menjalankan fungsinya sebagai panduan dalam mencari jalan menuju suatu tempat.
Prinsip navigasi pada Google Map adalah menentukan lokasi awal dan tujuan untuk selanjutnya ditentukan alternatif rute jalan yang dapat dilalui. Lokasi awal didapatkan dari penentuan posisi device menggunakan satelit GPS, sedangkan lokasi tujuan ditentukan berdasarkan titik yang sudah kita tentukan di peta. Dengan data jalan yang tersedia, Google Map akan menentukan beberapa alternatif untuk kemudian dipilih segmen jalan yang terpendek sebagai pilihan utama yang diberikan. Setelah itu, user dapat menggunakannya sebagai panduan untuk sampai ke tempat tujuan.
Konsep navigasi pada Google Map menggunakan algoritma Djikstra, yaitu algoritma untuk menentukan rute terpendek dari vertex awal ke vertex tujuan pada segmen-segmen garis tertentu. Secara sederhana, algoritma Djikstra dapat dijelaskan melalui gambar di bawah ini.
Algoritma Djikstra mensyaratkan vertex, edge, dan weight, dimana vertex adalah titik-titik yang saling terhubung, edge adalah garis yang menghubungkan antar titik tersebut dan mempunyai arah, sedangkan weight adalah jarak dari edge yang menghubungkan antar vertex. Vertex tersebut pada Google Map dianalogikan sebagai point-point yang merepresentasikan lokasi awal dan tujuan serta titik-titik lain yang menghubungkannya, sedangkan edge adalah segmen jalan yang dapat dilalui.
Atas dasar itulah, dalam pembuatan basisdata unsur transportasi, konsep topologi yang digunakan adalah harus terputus di pertemuan setiap segmen jalan. Jika merujuk pada aturan topologi yang tersedia di software ArcGIS, maka dapat digunakan aturan Must Not Intersect Or Touch Interior. Aturan itu memungkinkan seluruh pertemuan segmen jalan akan di-split, sehingga vertex-vertex bisa dihasilkan pada setiap persimpangan jalan.
Ketika persimpangan jalan sudah mempunyai vertex-nya masing-masing, maka opsi rute bisa ditentukan dengan benar, dan selanjutnya hanya bergantung pada jarak antar vertexyang ditentukan oleh shape length dari opsi segmen jalan yang mungkin untuk dilalui.
Oleh karena itulah, algoritma yang benar pada unsur transportasi akan sangat menentukan analisis spasial yang berkaitan dengan rute. Bisa dibayangkan ketika ada salah satu segmen jalan yang undershoot misalnya, dan network jalan tidak terbentuk di sana yang otomatis tidak ada vertex yang dihasilkan di titik yang seharusnya menjadi persimpangan jalan, maka rute jalan bisa jadi akan berputar lebih jauh. Ini tentu bisa menjadi kesalahan yang fatal, terlebih ketika analisis rute tersebut digunakan untuk kepentingan bisnis yang dapat mengakibatkan kerugian. Maka dari itu, topologi yang benar tentu mutlak untuk setiap fitur peta dasar agar user dapat mengoptimalkan peta tersebut secara maksimal.
Pada zaman teknologi ini, hampir semua orang pasti suah mengenali nama google maps. Google maps ini adalah suatu produk dari google yang berfungsi seperti sebuah peta. Namun google maps ini mencangkup seluruh permukaan bumi. Mungkin orang zaman sekarang kurang memiliki rasa ingin bertanya-tanya mengenai google maps namun, berbeda dengan zaman ketika google maps pertama kali muncul. Para pakar teknologi akan bertanya-tanya tentang algoritma yang mereka gunakan dalam aplikasi google maps ini
.
Google maps ternyata menggunakan sebuah algoritma yang dinamakan algoritma dijkstra. Algoritma ini berfungsi sebagai penentu rute terpendek yang harus ditempuh secara efisien. Algoritma ini dapat bekerja jika ada vertex, edge, dan weight. Vertex adalah titik-titik yang terhubung, edge adalah garis yang menyambungkan dari titik-titik tersebut, sedangkan weight memiliki arti jarak dari edge yang menghubungkan vertex.
Dalam menjalankan algoritma dijkstra pertama-tama algoritma ini harus mengetahui lokasi kita dan lokasi yang akan kita tuju (Vertex), yang kedua algoritma ini akan mencari semua rute yang dapat dilewati dari lokasi kita menuju lokasi yang akan kita tuju (Edge), dan yang terakhir algoritma ini akan memeriksa dan membandingkan rute-rute tersebut dan akan menampilkan rute tercepat yang dapat kita lalui dari lokasi kita menuju lokasi tujuan kita (Weight).
Referensi :
Algoritma merupakan urutan atau langkah-langkah untuk penghitungan atau untuk menyelesaikan suatu masalah yang ditulis secara berurutan. Sehingga, algoritma pemrograman adalah urutan atau langkah-langkah untuk menyelesaikan masalah pemrograman komputer. Yang akan kita bahas adalah algoritma yang digunakan dalam Google Maps.
Prinsip navigasi pada Google Map adalah menentukan lokasi awal dan tujuan untuk selanjutnya ditentukan alternatif rute jalan yang dapat dilalui. Lokasi awal didapatkan dari penentuan posisi device menggunakan satelit GPS, sedangkan lokasi tujuan ditentukan berdasarkan titik yang sudah kita tentukan di peta. Dengan data jalan yang tersedia, Google Map akan menentukan beberapa alternatif untuk kemudian dipilih jalan yang terpendek sebagai pilihan utama yang diberikan. Algoritma untuk menentukan jalan/rute terpendek ini menggunakan Algoritma Djikstra. Algoritma ini ditemukan oleh seorang Ilmuwan Komputer bernama Edsger W. Djikstra pada tahun 1956 dan diterbitkan tiga tahun kemudian. Djikstra menemukan algoritma ini saat menghirup aroma kopi dari suatu kedai kopi.
GIF diatas adalah bagaimana algoritma Djikstra bekerja.
Sumber :