Simple algoritma dijkstra dengan php

algoritma dijkstra dengan php

Sebelumnya saya pernah buat tutorial “cara mengimplementasikan algoritma dijkstra di android dan PHP menggunakan peta google map“. Bisa dibaca di link berikut (kalau tertarik) :

Implementasi algoritma dijkstra di android
Implementasi algoritma dijkstra di PHP

Nah kali ini saya mau share penerapan simple algoritma dijsktra di php. Artinya simple berarti cuma menampilkan hasil rute terpendeknya saja. Seperti gambar diatas hanya menampilkan jalur terpendek 0->2, tidak dengan map.

Untuk menggunakan simple algoritma dijkstra, yang diperlukan disini hanyalah 2 file php. Apa saja itu ?
1) Dijkstra.php
2) index.php

Oke langsung saja, berikut tutorialnya :

TUTORIAL

1) Pertama, download 2 file php dari sini
2) Kedua, kita akan mengkonversi sebuah graph ke dalam script php.

Misalkan saya punya graph seperti ini (terdiri dari simpul, jalur dan bobot jalur) :

Maka di file index.php, scriptnya seperti ini :

Penjelasan:

• $graph[0][0] = ‘1->10’; = artinya 0 pertama adalah simpulnya, 0 kedua adalah jalur. Kalau kita lihat $graph[0] terdiri dari [0][1][2] jalur, artinya ada 3 jalur yang mengarah dari simpul 0 ke simpul lain.  berarti dapat disimpulkan:
  • simpul 0 mengarah ke simpul 1 dengan bobot 10.
  • simpul 0 mengarah ke simpul 2 dengan bobot 11.
  • simpul 0 mengarah ke simpul 3 dengan bobot 40.

3) Selanjutnya kita test dengan menentukan simpul awal dan tujuan :
Pada baris 25, simpul awal kita set 0 dan simpul tujuan kita set 2. Anda bisa menggantinya dengan yang lain.

4) Jika di running, maka outputnya seperti ini :

Hasilnya tetap 0 -> 2, karena jalur yang terpendek dari simpul 0 ke 2 adalah 11.

Algoritma dijkstra yang saya buat ini cuma bisa menampilkan 1 kemungkinan jalur terpendek. Untuk yang bisa menampilkan semua kemungkinan jalur terpendek, saya belum buat scriptnya. Mungkin lain kali di tutorial yang berbeda.

Demikian tutorial algoritma dijkstra dengan php, Semoga bermanfaat!