Google Maps didasarkan pada algoritma yang sangat sederhana namun sangat efektif: algoritma Dijkstra. Ini mengambil namanya dari penemunya, Edsger Dijkstra, salah satu pendiri perintis komputasi modern. Perjalanan yang ditakdirkan untuk mengubah sejarah. Saat itu suatu pagi di tahun 1956 dan Dijkstra, yang saat itu bekerja sebagai programmer di Centrum Wiskunde & Informatica (CWI) di Amsterdam, sedang berjalan-jalan dengan pacarnya untuk berbelanja. Ketika mereka lelah berjalan, mereka duduk di sebuah kedai kopi, ilmuwan Belanda itu mendapat pencerahan: hanya dalam 20 menit, di depan secangkir kopi, ia merancang algoritma yang akan membuatnya memasuki sejarah ilmu komputer.

Untuk memahami cara kerjanya kita perlu mengenalkan konsep graf. Graf, seperti yang direpresentasikan pada gambar, adalah struktur yang dibentuk oleh node, diwakili oleh titik, dan busur, garis yang menghubungkan node. Meskipun sederhana, model ini dapat digunakan untuk menggambarkan banyak masalah. Misalnya, node dapat mewakili orang dan busur menghubungkan mereka yang saling mengenal; dalam anatomi, simpul dapat mewakili organ dan lengkungan pembuluh darah yang menghubungkannya, dalam astronomi, bintang adalah simpul yang, disatukan oleh lengkungan, membentuk rasi bintang. Dalam kasus kami, sebaliknya, lengkungan mewakili jalan, sedangkan simpul adalah persimpangan, itu semua titik di mana dimungkinkan untuk memilih jalan mana yang akan diambil.

Bagaimana peta menjadi grafik. Jalan-jalan adalah lengkungan (garis hitam), sedangkan persimpangan adalah simpul (lingkaran putih)

Lengkungan tidak semuanya sama. Ketika kita harus memilih di antara dua kemungkinan jalan, kita memperhitungkan jalan yang membawa kita ke tujuan terlebih dahulu. Faktor-faktor yang ikut berperan banyak: kecepatan maksimum, ukuran jalan, keberadaan lampu lalu lintas, lalu lintas dan sebagainya. Kami dapat meringkas semuanya dalam satu nilai, (perkiraan) waktu tempuh bagian itu. Informasi ini diintegrasikan ke dalam grafik kami berdasarkan bobot, yang merupakan nilai yang dikaitkan dengan setiap busur. Akibatnya, jika "4" ditulis pada busur yang menghubungkan simpul X dan simpul Y, ini menunjukkan bahwa untuk pergi dari persimpangan X ke persimpangan Y kami memperkirakan waktu yang dibutuhkan 4 menit.

Apa yang dilakukan algoritma Dijkstra? Mengingat grafik berbobot, titik awal dan titik akhir dalam grafik itu sendiri, algoritma menemukan "jalur minimum" yang menghubungkan dua titik, yaitu urutan busur yang meminimalkan jumlah bobot dan oleh karena itu, dalam kasus Peta, meminimalkan perkiraan waktu perjalanan.

Melihat lebih dekat.Agar berfungsi dengan baik, algoritme menyimpan "biaya" yang terkait dengan setiap node, yang mewakili nilai jalur minimum untuk mencapai setiap node. Sebelum memulai, node diberi biaya yang sangat tinggi, yang menunjukkan bahwa jalan belum ditemukan untuk mencapainya. Untuk semua orang kecuali node awal, yang ditetapkan dengan biaya nol (setelah semua, tiba di node keberangkatan dari node keberangkatan tidak dikenakan biaya!). Selain itu, ia menyimpan daftar semua node yang masih harus dikunjungi, yang pada awalnya mencakup semua node jaringan. Algoritma selalu mengulangi langkah yang sama. Pertama, ekstrak node dengan biaya terendah dari daftar node yang akan dikunjungi. Untuk setiap node yang belum dikunjungi pada jaringan yang dapat dijangkau dari node yang diperiksa, algoritme mengevaluasi berapa biaya untuk mencapai node ini. Jika biaya lebih rendah, maka diperbarui, jika tidak, dibiarkan tidak berubah, karena ada cara yang lebih nyaman. Node yang baru saja diperiksa ditandai sebagai dikunjungi dan mulai lagi, sampai node yang akan dikunjungi bukan tujuan.

Video ini menunjukkan contoh lengkap pengoperasiannya.

Algoritma Dijkstra selalu menemukan rute tercepat. Telah ditunjukkan secara matematis bahwa Dijkstra selalu menemukan jalur terpendek, selama setidaknya ada satu rute yang mungkin. Fakta ini terkadang bertentangan dengan kita: seringkali, pada kenyataannya, untuk menghemat beberapa detik, navigator mengirim kita ke jalan "alternatif" melawan akal sehat, dan bahwa kita tidak akan pernah memimpikan perjalanan. Namun, di sisi lain, ini sangat serbaguna, bahkan selalu dapat menemukan rute tercepat. Selain itu, dapat memperhitungkan informasi tambahan seperti informasi lalu lintas atau adanya kemacetan, cukup dengan mengubah bobot pada grafik. Tapi bagaimana Google mengetahui informasi lalu lintas? Gunakan data yang dikumpulkan oleh pengguna lain, tapi itu cerita lain

sumber: 

https://magazine-impactscool-com.translate.goog/en/speciali/google-maps-e-la-teoria-dei-grafi/?_x_tr_sl=en&_x_tr_tl=id&_x_tr_hl=id&_x_tr_pto=sc