2

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

Ambar Hasbiyatmoko

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

2 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.

Comments are closed.