Rute terbaik dengan Algoritma Dijkstra dan Google Map API

216

Rute terbaik dengan Algoritma Dijkstra dan Google Map API

 

Ada yang kebingungan cari contoh kode implementasi dijkstra menggunakan gmap. Untuk kasus menentukan rute dengan mempertimbangkan node berupa persimpangan jalan, saya pikir inilah kode yang agak tepat.

Saya temukan kode ini di github. Beberapa kode lain saya download dan saya coba. Tapi inilah yang terbaik.

https://github.com/venkat-abhi/Graph-routing-using-dijkstra-shortest-path-algorithm-and-google-maps

 

https://github.com/venkat-abhi/Graph-routing-using-dijkstra-shortest-path-algorithm-and-google-maps

 

Kita lihat tampilannya Rute terbaik dengan Algoritma Dijkstra dan Google Map API

Ini tampilan ketika dijalankan Rute terbaik dengan Algoritma Dijkstra dan Google Map API

 

Ini data node persimpangan jalan. Dalam js.

 

Ini algoritma dijkstra dalam Js.

 

Algoritme Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritme rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritme ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

Bobot (weights) dari semua sisi dihitung dengan fungsi

w: E → [0, ∞)

jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.

Ongkos (cost) dari sebuah sisi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritme ini menghitung jarak terpendek dari s ke t.

Anda mungkin ingin membaca ini