139

Implementasi algoritma dijkstra di PHP

Hello ๐Ÿ™‚ , Kali ini saya mau share bagaimana cara mengimplementasikan algoritma dijkstra menggunakan PHP, mysql dan google map.

implementasi algoritma dijkstra di php mysql google map

Sebelumnya saya juga pernah buat tutorial algoritma dijkstra di android, Tapi kayaknya kurang greget kalau cuma buat tutorial di androidnya saja, masa di php ngga? haha ๐Ÿ˜€

Sebelum masuk ke tutorial, ini penampakan aplikasinya yang sudah jadi :

Untuk membuat aplikasi ini, requirementnya adalah :
1) PHP versi 5.4 ke atas (yang support mysqli dan PDO)
2) Google Maps v3
3) Mysql

So, buat yang versi PHPnya masih 5.3 ke bawah, upgrade dulu ke > 5.4. Kalo gak diupgrade ngga bakalan jalan aplikasi ini.

TUTORIAL

– Mengkonversi Graph ke dalam Peta

Misal saya punya graph seperti ini :
graph with distance and arrow

Langkah pertama yang kita lakukan adalah mengkonversi graph tersebut ke dalam peta. Caranya?

Caranya sebagai berikut :

1) Buka graph.latcoding.comgraph for phpDisitu ada beberapa tools :
a) Add Node
Membuat node/simpul
b) Add Line
Membuat edge/jalur
c) Add Destination
Menambahkan tempat yang ingin dituju (misal sekolah, rumah makan, dll)
d) Add Route
Menambahkan rute angkutan umum pada graph
e) Generate SQL
Meng-konversi graph ke format .sql

2) Pertama kita akan buat node/simpul terlebih dulu, klik ‘Add Node’ sampai ada tanda [x], lalu buat node sesuai dengan keinginan Anda. Contohnya saya membuat 4 node :
buat nodes graph secara online(*Klik marker untuk melihat nomor node)

Nah gambar di atas kita menamai nodenya mulai dari 0, 1, 2, 3 dst. Kenapa gak pakai huruf saja? misal a, b, c, dst ..? Hm, kalau pakai huruf itu terbatas hanya 24 saja. Lebih baik pakai angka gan, cepat dan praktis.

3) Selanjutnya kita buat jalur, klik ‘Add Jalur’ klik marker nomor 0, lalu mulailah membuat jalur sampai ke marker nomor 1 :
create edge graph via online– Lanjutkan buat jalur dari marker nomor 3 sampai ke nomor 1 :
graph tiga ke satu– Lanjutkan buat jalur dari marker nomor 2 sampai ke nomor 1, sehingga jalur sudah terbuat semua seperti ini :
membuat graph secara online ke format sql

4) Langkah selanjutnya kita buat lokasi tujuan atau destination. Dalam tutorial ini saya membuat lokasi tujuan berupa lokasi SMK atau SMP.
Klik ‘Add Destination’, lalu tentukan lokasinya :
create destination graphSecara default, nama lokasi tujuan di set mulai dari a, b, c, dst. Untuk merubahnya klik namanya, lalu akan muncul popup, ganti namanya lalu tekan OK.
ganti nama destination pada graphSetelah diubah :
lokasi sekolah pada graph algoritma dijsktra– Lanjutkan membuat lokasi tujuan :
membuat rute pada graf graph
4) Selanjutnya kita akan buat rute angkot dari graph tersebut.
Klik ‘Add Route’ maka akan muncul kotak inputan :
buat rute angkot pada graf

Nah cara membuat rute angkotnya harus sesuai format, yaitu :

nama_kendaraan=simpul_yang_dilewati

Misalkan saya disini mau membuat rute angkot untuk angkot ‘T01’ dengan rute mulai dari node 0 menuju node 1, lalu dari node 1 ke node 3, dari node 3 balik lagi ke node 1, 1 ke node 0.
alur angkot pada graphMaka dapat ditulis seperti ini :

T01=,0-1,1-3,3-1,1-0,

Dan saya buat 3 rute angkot seperti ini :
alur dari angkot pada graph

5) Setelah graph selesai dibuat, sekarang tinggal export graph ke .sql.
Klik ‘Generate SQL’, maka file .sql akan terdownload.
download graph to sqlUntuk yang mau sample .sqlnya bisa download dari sini

graph.sql

**Langkah selanjutnya kita akan import file sqlnya lewat phpmyadmin

– Import .SQL

1) Buat database dengan nama ‘algo_dijkstra’
create database dijkstra
2) Import file .sql yang barusan Anda download.
Klik tab ‘import’ > lalu choose file sql > save
import sql graphLalu akan terbuat 3 tabel, yaitu tabel angkutan_umum, graph, dan sekolah :
tiga tabelNah, urusan database untuk graph sudah selesai sampai sini, tahap selanjutnya tinggal download project aplikasi dijkstra yang sudah saya buat.

– Download dijkstra-algorithm via github

1) Saya sudah buat aplikasi dijkstra-nya di github, silahken download dari sini.
2) Setelah terdownload, lalu ektrak. Akan ada folder ‘dijkstra-algorithm-master‘. Ganti nama foldernya menjadi ‘algo_dijkstra‘ lalu copy folder tersebut ke dalam folder htdocs.
dijkstra algorithm master3) Selanjutnya, kita harus setting koneksi ke database dulu. Buka file Koneksi.php, lalu setting sesuai database Anda.
algo_dijkstra setting koneksi pada graph

– Test Aplikasi

Sekarang tinggal test aja aplikasinya, buka url :

http://localhost/algo_dijkstra/

Cara menggunakannya :
1) Tap pada peta untuk menentukan lokasi Anda
2) Pilih lokasi tujuan Anda.
3) Klik RUN.

implementasi algoritma dijkstra di php mysql dan google maps

TUTORIAL VERSI VIDEO

[related_post themes="text" id="1371"]

Ambar Hasbiyatmoko

Hello, I'm web developer. Passionate about programming, networking and web server. @kaskus  @facebook

139 Comments

  1. thank you buat postingannya kak^^
    saya juga lagi nyari referensi buat tugas terus nemu blog ini. tapi tugas saya lebih simple, hanya menampilkan hasil rute terpendek tanpa peta. nah kira-kira, untuk menyimpan data jaraknya perlu mysql atau tidak? saya lihat dari referensi lain, ada yang langsung memasukkan data jaraknya ke kode phpnya.

  2. jika di php dibagian mana yg di looping 3x mas? saya tes yg php dg mysql

  3. Gan , kok rutenya gak mau kluar ya ?
    saya kasih titik awal 21
    dengan destinasi 20 titik
    apakah ada batas maximal jumlah graphnya ?
    terimakasih

    • klo rute ngga keluar kemungkinan ada error, cek errornya .. klik kanan > inspect > tab console .. lihat errornya .. lalu share dimari ..

      maksimal jumlah node = 100 mas bro ..

  4. terimakasih mas, sangat membantu. oh iya, kalau seandainya mau ditambahkan jarak tempuh dan titik yang dilewati setelah rute muncul kira2 bisa nggak ya mas? mohon pencerahannya.

    • bisa mas .. modif aja scriptnya di https://github.com/mokox/dijkstra-algorithm/blob/master/Main.php
      – line 197 tambahin $jarak_tempuh = 0;
      – line 200 edit jadi SELECT jalur, bobot …….. dst
      – line 203 tambahin $jarak_tempuh += $fetch[‘bobot’];
      – line 228 edit jadi [‘jalur_shortest_path’=>$semua_latlng, ‘angkot’=>$angkot_array, ‘bobot’=>$jarak_tempuh];

      *note: scriptnya belum saya coba .. tp logikany seperti itu.

  5. Bang Minta email nya dong.. ada problem tentang peta ga keluar nih, mau ane kasih liat via screenshot masalah nya.. hehe, makasih mas

  6. minta emailnya dong mas, ane mau minta bantuan ni kalo dicobain pake framework

      • oalaah.. kalo boleh minta script yg toolsnya dong mas, yg add node add line add route add destination generate sql, nanti saya coba, lg buat skripsi iini mas -,-

  7. Mas, mohon dicerahin nih saya.
    Kalau di localhost muncul rutenya ketika klik tombol run. Tapi di hosting online kok tdak muncul ya. Terimakasih. Mohon dicerahin mas ๐Ÿ™‚

  8. gan , sangat membantu gan, tapi bisa gak gan , keluar jaraknya , ane uda coba modif di main.phpnya yg di line 197, 200 , 203 , 228 malah ancur gan, hehehe maaf ngrepotin gan,

  9. Misal saya buat rute terus singkat cerita saya generate sql, terus saya terapkan ke web offline. Terus pas di tengah jalan saya ingin menambahkan data tempat lagi. Apa saya harus buat dari awal atau bisa mengedit dari sintax yang sudah ada mas? terima kasih sebelumnya

    • Terimakasih bang, tutorialnya sangat membantu. Kalo untuk tools addnode,addline,adddestination dg addroute, apa ad tutorialnya?. mohon pencerahan nya bang.Terima kasih

    • @asep buat lagi dari awal bro, utk sekarang fasilitas di graph.latcoding.com cuma create doank blum ada edit

  10. Saya udah ikuti langkah-langkah diatas , tapi rute nyah gg nampil , kenepa yaa mass ??

      • php saya sudah 7.09 mas tetapi jalur ttp tdak tampil
        pesan error:
        Uncaught SyntaxError: Unexpected token < in JSON at position 0
        at JSON.parse ()
        at Object.success (index.php:144)
        at j (jquery.js:3099)
        at Object.fireWith [as resolveWith] (jquery.js:3211)
        at x (jquery.js:8264)
        at XMLHttpRequest. (jquery.js:8605)

  11. Assalamu’alaikum wr.wr.
    Mau tanya gan ini kenapa punya saya kok maps nya nggak bisa nampil dan muncul tulisan kaya gini,
    (Oops! Something went wrong. This page didn’t load Google Maps correctly. See the JavaScript console for technical details.)
    padahal buatnya sudah sesuai dengan tutornya, tetapi koordinatnya saya ganti di wonosobo.
    Terima kasih
    Wassalamu’alaikum wr.wb

    • @asep buat bedain row yg sementara atau yg permanen
      kalo temp = Y berarti row sementara, di create dr system
      kalo temp = N berarti row ‘jalur’ (permanen) yg mas bro buat dr graph.latcoding.com

  12. Bang pas saya klik tombol run muncul erorr “error: [object Object]”, itu apa ya masalahnya. mohon pencerahannya bang. Terima kasih

  13. Bang kalau penggabungan naik angkutan umum 2 kali naik angkot. kira kira bisa di implementasiin ga yah..hehe

  14. Gan bisa gk pas di generate SQL, nama tabel sekolah diganti jadi nama tabel lokasi ? mohon bantuanya Gan.

    • utk saat ini blm bisa mas, .. paling klo mau ganti nama tabel, tinggal buka file.sqlnya, ganti “create table sekolah” ke “create table lokasi”

  15. Gimana Cara Mengatasi erorr kayak ni mas bro?
    Oops! Something went wrong.
    This page didn’t load Google Maps correctly. See the JavaScript console for technical details.

  16. algoritma dijstrak itu cocoknya untuk angkot yah..
    kalau saya mau buat bikin mencari lokasi bisa ga?
    atau apa metode yang cocok untuk mencari sbuah lokasi .. maksih

    • algoritma dijkstra itu buat dapetin jalur terpendek, jadi kalo buat pencari lokasi bserta “JALUR”nya juga, km bisa pake algoritma dijsktra ini.

  17. Assalamualaikum,
    gan ane mau tanya,
    pas di run line nya ga muncul, kenapa yaa ?
    ane pake php 5.6
    gimana ngatasinya ?

    • scra garis besar begini :

      1) dapatkan dulu koordinat user dan tujuan.
      2) kemudian, cek koordinat user lbih dekat dengan node yg mana(yg ada pada graph).. ? misal didapat node 5.
      3) cek juga koordinat tujuan, dekat dgn node yg mana? misal didapat node 2.
      4) setelah node source(5) dan node destination(2) didapat, lakukan perhitungan algoritma dijkstra
      5) return dari algo dijkstra berupa jalur terdekat, (misalnya) 5->4->3->2, artinya jalur terdekat melewati node 5, lalu 4, 3 dan 2.
      6) tahap terakhir.. gambar jalurnya ke google maps, caranya :
      – cari jalur dari node 5 ke 4 dari database (select jalur from graph where simpul_awal = 5 and simpul_tujuan = 4)
      – cari jalur dari node 4 ke 3 dari database.. begitu seterusnya sampai 3 ke 2.

      klo mau detail lagi, bs lbh panjang lagi .. hha

      • mantap gan makasih hee
        terus gan itu di codinganya ada json json, buat apa sih itu? he

  18. Terimakasih atas share ilmunya mas, saya ada pertanyaan tentang algoritma ini. apakah hasil dari jarak ini datanya bisa ditarik ke database? terimakasih

  19. mas ini kan lokasinya di jakarta. kalau ngubah lokasi nya seusai yg diinginkan dimana ya mas

    • di index.php, latitude longitudenya diganti :

      function initialize() {
      /* setup map */
      var mapOptions = {
      zoom: 13,
      center: new google.maps.LatLng(-6.2858667, 106.8719382)
      };
      …..

  20. pertama map nya gk muncul terus saya ganti maps api key nya.. sekarang map nya dah muncul.. tp saat sudah ditentukan lokasi dan tujuan jalur nya gk muncul.. tolong bantuan nya mas…

  21. ada error begini gmn gan

    Parse error: syntax error, unexpected ‘[‘, expecting ‘)’ in C:\xampplite\htdocs\dijkstra-algorithm-master\Main.php on line 69

    • Cek versi PHPnya .. Diartikel diatas kan dah dkasi requirementnya gan pake PHP versi berapa.

  22. saya mau membuat misalkan ada tiga buah tempat jka A,B,C memenuhi kondisi semua tujuan di lewati Jika tidak misal kan B tidak memenuhi kondisi maka yang dilewati hanya A dan C
    bisakah itu di implementasikan mas ???
    Terimakasih atas waktunya mas

  23. Mas rute nya gak muncul, setelah di inspect ada error
    SyntaxError: JSON.parse: unexpected character at line 1 column 1 of the JSON data. (line 144:15)
    mohon bantuannya mas…

      • db nya itu yg saya download di web ini mas, semua file sama (standard) gak ada saya ubah2 mas, sesuai dengan tutorial nya. Saya coba pake chrome errornya jd begini mas :
        Uncaught SyntaxError: Unexpected token < in JSON at position 0
        at JSON.parse ()
        at Object.success ((index):145)
        at j (jquery.js:3099)
        at Object.fireWith [as resolveWith] (jquery.js:3211)
        at x (jquery.js:8264)
        at XMLHttpRequest. (jquery.js:8605)

      • @mas ambar dan @mas wiro
        sudah ketemu mas permasalahannya ada di file koneksi.php di line 6 dan 10 nya dihapus password nya. Sebelumnya saya hanya menghapus di line 6, setelah di lihat di network rupanya ada password lagi di line 10. setelah saya hapus udah bisa mas. ๐Ÿ™‚

  24. om, untuk script generate node,line, destinationnya itu di share donk om, soalnya gak bisa di akses euy,
    sama mau nanya nih, misalnya
    saya buat jalur angkot a dan b itu hampir sama tapi bedanya jalur b belok ke kanan pada suatu perempatan, dan angkot a lurus, nah ketika dipeempatan itu, angkot c lewat juga dari arah angkot b ketik angkot b belok kanan menuju lurus atau sebanding dengan jalur angkot a dan b jika belok kiri ketika per empatan, sementara destinasi yang ingin dituju itu dari jalur angkot a dan b, namun ketika diperempatan jalur destinasinya menggunakan angkot C
    intinya supaya bisa naik 2 angkot ke tujuannya
    jika hanya pakai dijkstra saja, pasti jalur berhenti di perempatan itu, adakah saran mas ? buat pembelajaran hehe
    terimakasi

  25. Mas dari node 1 ke node lainnya kan pake jarak yah, jarak nya itu dalam bentuk apa ya? Meterkah? Bisa d lihat tidak? Terimkasih

    • iya benar dlm meter .. klo mo lihat ada di DBnya, di table graph, field bobot ..
      klo mo dimunculin ke view tinggal query aja where nodenya berapa ..

  26. Mas ambar, pas saya buat db yang banyak data angkutan umum = 21, graph =84, sekolah=21. malah jadi error seperti ini mas :
    inspect console:
    Uncaught SyntaxError: Unexpected token < in JSON at position 0
    at JSON.parse ()
    at Object.success ((index):145)
    at j (jquery.js:3099)
    at Object.fireWith [as resolveWith] (jquery.js:3211)
    at x (jquery.js:8264)
    at XMLHttpRequest. (jquery.js:8605)
    success @ (index):145
    j @ jquery.js:3099
    fireWith @ jquery.js:3211
    x @ jquery.js:8264
    (anonymous) @ jquery.js:8605

    inspect network:
    Notice: Undefined offset: 1 in C:\xampp\htdocs\algo_dijkstra\Dijkstra.php on line 277
    Notice: Undefined offset: 24 in C:\xampp\htdocs\algo_dijkstra\Dijkstra.php on line 277
    Notice: Undefined offset: 1 in C:\xampp\htdocs\algo_dijkstra\Dijkstra.php on line 321

    pas saya ganti sama db yg datanya masih sedikit programnya jalan mas.
    mohon bantuannya mas, lagi skripsi ~.~

  27. Mas misalkan kita buat 4 tujuan
    Untuk melewati semua tujuan dalam sekali jalan bisa ga mas
    1 tujuan hanya d lalui 1 Kali saja
    Makasih sebelumnya mas

    • bisa aja si mas klo scriptnya dikembangin, brarti 4 kali ngjalanin algo dijkstra, krna ada 4 tujuan.
      cm utk script yg skrg blm bs mmnuhi kbtuhan tsb.

  28. mas mau tanya kalo mau menampilkan semua objek tujuan gimana mas,jadi ga satu-satu.

  29. Assalamuallaikum, terima kasih sangat membantu ๐Ÿ™‚
    kebetulan lagi cari referensi buat tugas Akhir, boleh minta emailnya buat konsultasi mas ? terima kasih ๐Ÿ™‚

  30. gan cara ganti kordinat graph.latcodig.com yang dari dari jakarta mau saya pindah ke lokasi saya . gimana gan caranya ?

    • ngga bisa lah mas, kan scriptnya di graph.latcoding.com ..
      paling bisanya digeser itu peta ke arah lokasi mas. Coba geser aja ke kanan kiri.

  31. mas mau tanya kalo mau menampilkan semua objek tujuan gimana mas,jadi ga satu-satu. jadi nampilin semua marker di radius user. makasi sebelumnya sangat bermanfaat ilmunya

  32. asslamuaikum bang.
    mau tnya untuk lokasi awal sesuai koordinat gps kita bisa tidak ya?

  33. asalamualaikum wr wb selamat malam mas saya mau tanya saya coba membuat aplikasinya ko ada pesan error
    Notice: Use of undefined constant MYSQL_ASSOC – assumed ‘MYSQL_ASSOC’ in D:\localhost\htdocs\w\GraphToArray.php on line 63

    Warning: mysqli_fetch_array() expects parameter 2 to be integer, string given in D:\localhost\htdocs\w\GraphToArray.php on line 63

    ini masalahnya apa ya

  34. Mas mohon bantuannya, saya masih gak ngerti gimana konversi graph ke dalam bentuk array dua dimensi. di file GraphToArray.php bagian komentar line 24 sampai 32. Bisa dijelaskan mas? saya belum paham. Terimakasih

    • iya harus dikonversi jadi array .. soalnya nanti perhitungan algo. dijkstranya di PHP ..
      jadi di PHP nanti di looping array tsb, untuk mndptkan jarak terpendek. ..

  35. permisi mas kok di tempatku muncul erornya
    Use of undefined constant MYSQL_ASSOC โ€“ assumed โ€˜MYSQL_ASSOCโ€™ in D:\xampp\htdocs\algo_dijkstra\GraphToArray.php on line 63
    trus ada lagi
    mysqli_fetch_array() expects parameter 2 to be integer, string given in D:\xampp\htdocs\algo_dijkstra\GraphToArray.php on line 63
    ada apa yaa ?mohon bimbinganya suhu

    • di json_decode($json) dulu, baru di foreach di phnya.. trus masukin dah datanya ke file.sql pake fopen & fwrite

  36. Assalamualaikum mas, tlong share dong yg pke algoritma greedy ๐Ÿ™‚
    thanks before ๐Ÿ™‚

  37. Malam Mas Ambar, terimakasih untuk sharing ilmu seputar dijkstar dan gis khususnya. Terkait tutorial itu saya implementasikan kedalam saya punya tugas.

    Problem saya ketika RUN respon nya SyntaxError: JSON.parse: unexpected character at line 1 column 1 of the JSON data[Learn More]

    Mohon diberikan arahan dan ketepatan atas solusi nya

    Ditunggu bangeeeet mas terimakasih

  38. mas saya udah coba di localhost menggunakan xampp jalan , cuma saat saya coba upload di hosting tidak jalan, ada pesan “Alur graph Anda Salah” kira2 salahnya apa y?

  39. Sebelumnya terimakasih atas infonya ini, sangat membantu. Mas, saya sudah mencoba membuat, tetapi saya sudah merubah API Key nya tetapi Map nya tetap tidak muncul. Padahal sudah sesuai dengan petunjuk. Bagaimana solusinya?
    Selain itu muncul pemberitahuan yang seperti ini:
    Warning: mysqli_connect(): (HY000/1045): Access denied for user ‘root’@’localhost’ (using password: YES) in E:\xampp\htdocs\googlemaps_algo_dijkstra\Koneksi.php on line 6

    Warning: mysqli_connect(): (HY000/1045): Access denied for user ‘root’@’localhost’ (using password: YES) in E:\xampp\htdocs\googlemaps_algo_dijkstra\Koneksi.php on line 6

    Warning: mysqli_query() expects parameter 1 to be mysqli, boolean given in E:\xampp\htdocs\googlemaps_algo_dijkstra\Main.php on line 32

    Terimakasih.

  40. Same problem as mention by RAAFINDRA REVELATION

    Uncaught SyntaxError: Unexpected token < in JSON at position 0
    at JSON.parse ()
    at Object.success ((index):146)
    at j (jquery.js:3099)
    at Object.fireWith [as resolveWith] (jquery.js:3211)
    at x (jquery.js:8264)
    at XMLHttpRequest. (jquery.js:8605)

    • versi PHPnya mesti 5.4 keatas … kan udah saya jelasin ditutorialnya ..
      cb baca lagi yang teliti.

  41. Sebenarnya saya menggunakan PHP 7. heei @AMBAR HASBIYATMOKO saya juga sudah mengirim email ke alamat email “x@ambar-hasbiyatmoko.com”. Saya telah menunjukkan di mana saya menghadapi masalah tersebut. Silakan melalui email.

  42. tolong tonton video.Here ini masalahnya Saya menggunakan PHP 7, berarti tidak ada masalah dengan versi PHP, sesuatu yang lain …

    • klik kanan page > inspect > tab network > jalankan aplikasi > lihat error yang warna merah > share errornya disini, nanti saya bantu

      • Heei I send you the network records .Can you now find the error.I have also shared the source code file.

  43. gan ane kan udh ikutin saran agan yang biar nampilin jarak tempuh nya . tapi ko malah gagal yaa? minta pencerahan nya dong gan.

    • untuk yang di line 200 saya kurang paham gan.
      $select = “SELECT jalur FROM graph where simpul_awal =” . $exp_shortest_path[$start] . ” and simpul_tujuan =” . $exp_shortest_path[(++$start)];

      untuk penambahan bobot dan jalur tuh gmn yaa gan script nya . bisa dituliskan gan?

  44. Assalamualaikum mas kalo perintah penentuan lokasi awal dengan “click” itu diganti dengan penentuan lokasi awal dengan gps bisa ndak ya?

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.