AGENDA
Tutorials - Algoritma
Algoritma Dijkstra & Implementasinya



Pencarian rute terpendek termasuk ke dalam materi teori graf. Algoritma yang sangat terkenal untuk menyelesaikan persoalan ini adalah algoritma Dijkstra. Algoritma ini ditemukan oleh seorang ilmuwan komputer berkebangsaan Belanda yang bernama Edsger Dijkstra. berikut ini adalah pseudo code dari algoritma Dijkstra (Jong Jek Siang,2004).

Pseudo code Algoritma Dijkstra

procedure dijkstra (w,a,z,L)
    L(a) := 0
    S := { }
    
    for semua verteks x≠a do
        L(x) := ∞

    T := himpunan semua vertex
        
    while z(T) do
    begin
        pilih v(T) dengan minimum L(v)
        T:= T-{v}
        S:= S union {v}

        for setiap x(T di samping v do
            L(x):=min{L(x), L(v)+w(v,x)}
    end
end dijkstra

 

Dijkstra adalah algoritma yang digunakan untuk mencari lintasan terpendek pada sebuah graf berarah. Contoh penerapan algoritma djikstra adalah lintasan terpendek yang menghubungkan antara dua kota berlainan tertentu (Single-source SingledestinationShortest Path Problems). Cara kerja algoritma Dijkstra memakai stategi greedy, di mana pada setiap langkah dipilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan simpul lain yang belum terpilih. Algoritma Dijkstra membutuhkan parameter tempat asal, dan tempat tujuan. Hasil akhir dari algoritma ini adalah jarak terpendek dari tempat asal ke tempat tujuan beserta rutenya.

Baiklah, sekarang mari kita mulai untuk implementasi algoritma Dijkstra ini pada PHP dan MySQL.

1. Install Localhost

Banyak aplikasi yang dapat digunakan dalam membangun webserver pada localhost. Di tutorial ini saya akan menggunakan XAMPP versi portable. Untuk aplikasinya dapat diunduh di situs resminya : Apache Setelah selesai mengunduh aplikasi XAMPP tersebut selanjutnya ekstrak pada direktori (Folder) yang akan anda jadikan localhost.


[Gambar 1]

 

Pada tutorial ini saya menggunakan lokasi ektrak di drive (D:), setelah di ekstrak maka akan muncul folder [xampp] di drive (D:) anda.


[Gambar 2]

 

Setelah folder xampp terekstrak pada drive (D:), maka double click folder agar anda masuk ke dalam folder dan cari file [xampp_control.exe].

[Gambar 3]

 

Double click file tersebut agar aplikasi berjalan.


[Gambar 4]

Pada form aplikasi di atas, klik tombol admin pada module apache, yang sebelumnya pastikan module apache dan mysql terblok dengan warna hijau yang berarti kedua module terebut telah berhasil jalan pada komputer anda. Setelah anda mengklik tombol admin maka akan muncul halaman web XAMPP yang berjalan pada localhost anda.


[Gambar 5]

Klik menu security pada halaman di atas. Maka akan muncul halaman baru. Jika telah muncul halaman di bawah, maka klik tautan yang di tunjuk.


[Gambar 6]

 

Isi password anda untuk root user. Jika ini adalah pertama kali anda menginstall maka anda hanya akan mengisi new password dan repeat password. Notes: pastikan anda mengingat password tersebut, karna akan anda gunakan untuk mengakses database.


[Gambar 7]

 


[Gambar 8]

 

2. Perancangan Database dengan MySQL

Berikutnya kita masuk ke perancangan database dengan cara mengetik alamat seperti pada gambar di browser anda.

[Gambar 9]

 

Jika mysql anda berjalan normal, maka anda akan melihat halaman form login phpmyadmin. Masukan user root dengan password yang anda buat tadi.


[Gambar 10]

Setelah anda berhasil masuk, klik tab database seperti di bawah ini:


[Gambar 11]

 

Lalu buat database dengan nama “dijkstra”. Dengan penyortiran (Collation) “utf8_general_ci”. Lalu klik [create].


[Gambar 12]

 

Berikutnya buat tabel, yang akan secara otomatis tampil setelah anda membuat sebuah database.


[Gambar 13]

 

Buat nama tabel “jarak” dengan kolom “4”.


[Gambar 14]

 

 

Lalu isikan lah field sesuai dengan gambar di bawah ini.


[Gambar 15]

 

 

Setelah itu, klik [save].


[Gambar 16]

Lalu selanjutnya buat tabel kedua dengan nama “kota” dengan jumlah field “2” dan isi field sesuai dengan gambar di bawah.
[Gambar 17]

 

 

Lalu klik save, maka akan muncul tampilan seperti berikut.


[Gambar 18]

 

 

Klik [insert] pada tab tabel kota, dengan jumlah row 10.


[Gambar 19]

 

 

Isi daftar nama kota seperti berikut, anda cukup mengisi nama kota saja, anda tidak perlu mengisi id_kota.


[Gambar 20]

 

 

Jika berhasil maka akan muncul tampilan berikut.


[Gambar 21]

 

 

Setelah itu maka klik tabel jarak dan klik [tab insert], lalu isikan data di bawah sesuai dengan tampilan yang telah saya buat.


[Gambar 22]

 

 

Masukan data seperti gambar berikut.


[Gambar 23]

 

 

Jika anda berhasil, maka sekarang lanjutkan ke tahap berikutnya.

 

3. Implementasi Dijkstra pada PHP

Untuk mengimplementasikan Dijsktra pada PHP, saya menggunakan library Open Source yang bisa anda download pada alamat berikut.

Lib-Dijkstra klik ZIP untuk mendownload file library. (Link Alternatif)


[Gambar 24]

 

 

Ekstrak file zip yang anda download ke dalam folder localhost anda. Pada kasus ini saya menggunakan dir : [D:\xampp\htdocs\Dijkstra\lib\]. Jika direktori belum ada pada localhost anda, silahkan di buat dahulu folder yang bersangkutan.


[Gambar 25]

 

 

Setelah di ekstrak maka akan ada dua file di dalam dir lib.


[Gambar 26]

 

 

Agar memudah membuat file php nantinya, silahkan atur properties folder option pada explorer anda. Seperti berikut: Hilangkan centang pada pilihan [hide extentions for known file types].


[Gambar 27]

 

 

Setelah itu klik kanan pada explorer anda, pilih [New-text document], ganti nama file tersebut dengan [index.php]. lalu klik dua kali file index.php


[Gambar 28]

 

 


[Gambar 29]

Ketikan/copykan code di bawah ke dalam file index.php

<?php

/*
 * Author     : Virues Galau
 * Supported by : Green Belt of Aplysit Team
 */

// panggil class dan fungsi Dijkstra
require_once("lib/PriorityQueue.php");
require_once("lib/Dijkstra.php");

// buat koneksi ke database mysql
$connectToDb = mysql_connect('localhost', 'root', '[isi dengan password anda]');
if (!$connectToDb) {
    die('Gagal Konek ke database: ' . mysql_error());
}

// select database
mysql_select_db("dijkstra");

//buat query mysql untuk mengambil data pada tabel kota
$result = mysql_query("select * from kota");

// buat var kota untuk menampung data kota
$kota = array();

while ($row = mysql_fetch_array($result, MYSQL_ASSOC)) {
    $kota[$row["id_kota"]] = $row["kota"];
}

// bersihkan var $result dari data sebelumnya
mysql_free_result($result);

// inisialisasi var $g sebagai kelas Graph - Dijkstra
$g = new Graph();

// periksa var GET, apakah telah di isi
if (isset($_GET["asal"]) AND isset($_GET["tujuan"])) {
    
    //buat query mysql untuk mengambil data pada tabel jarak
    $result = mysql_query("select * from jarak");
    
    // ekstrak data dari database
    while ($row = mysql_fetch_array($result, MYSQL_ASSOC)) {
        
        // tambah titik pada graph (var $g)
        $g->addedge($kota[$row["asal"]], $kota[$row["tujuan"]], $row["jarak"]);

        // titik balik dari titik yang di defenisikan
        $g->addedge($kota[$row["tujuan"]], $kota[$row["asal"]], $row["jarak"]);
    }
    
    // masukan data ke var $distances dan $prev sebagai list
    list($distances, $prev) = $g->paths_from($_GET["asal"]);
    
    // inisialisasikan var $rute, $rutes, dan $jarak
    $rute = "";
    $rutes = $g->paths_to($prev, $_GET["tujuan"]);
    $jarak = $g->paths_to($distances, $_GET["tujuan"]);
    
    //ekstrak data dari var $rutes
    foreach ($rutes as $value) {
        if ($value != $_GET["tujuan"]) {
            // masukan data hasil ekstaksi ke dalam var $rute
            $rute = $rute . $value . " => ";
        } else {
            $rute = $rute . $value;
        }
    }
    
    // tampilkan hasil ke browser
    echo "Rute terdekat antara kota " . $_GET["asal"] . " dengan kota " . $_GET["tujuan"] . " adalah :";
    echo $rute . " ";
    echo "dengan jarak sejauh " . $jarak[0] . " Km";
}

//tutup koneksi database
mysql_close($connectToDb);

?>

Setelah anda ketik atau copykan code di atas maka jalankan aplikasi melalui web browser anda. Dengan mengetik alamat berikut pada

address bar : http://localhost/Dijkstra/?asal=A&tujuan=J

jika tidak terjadi error maka akan tampil seperti gambar di bawah ini.


[Gambar 30]

 

 

Dari tampilan di atas dapat dilihat hasil dari perhitungan dengan menggunakan algoritma Dijsktra. Demikian penjelasan tentang algpritma Dijkstra, sampai bertemu pada lain kesempatan.

Like or Share This Article




COMMENTS ( 0 )
./foto_users/small_no_avatar.jpg
Comment #1
husnul mafar 09 Januari 2015 (10:41:35)
saya mau bertanya gan........
link lib nya not found.....
ada link yang terbaru atau bisa di download g' ya ???

./foto_users/small_89aplysit.jpg
Admin Aplysit 18 Maret 2015 (23:08:01)
ini link alternatifnya gan. yang aslinya sudah dihapus sama pemiliknya.

LINK

./foto_users/small_no_avatar.jpg
Comment #2
ahmad 24 Mei 2015 (14:39:57)
mas setelah saya coba saya memiliki gendala error pada baris ke 45

Fatal error: Class 'Graph' not found in C:xampphtdocscoba_dijkstraindex.php on line 45

untuk database udah saya coba samakan..
gmna ya mas? mohon bantuannya 

./foto_users/small_no_avatar.jpg
Comment #3
theo 14 November 2015 (01:27:35)
Pak, mau tanya. kalo untuk perbandingan jaraknya pada bagian mana ya?
dan satu lg, apakah djikstra ini sama dengan algoritma greedy?

Terima Kasih

 
Keep connected with us, mobile apps available now !!