Journal Basic Science And Technology, 1(2), 30-34,2012 ISSN : 2089-8185
Rancang Bangun Aplikasi Web Pencarian Rute Terpendek Antar Gedung di Kampus Menggunakan Algoritma Floyd-warshall Lutfi Fanani Program Teknologi Informasi dan Ilmu Komputer Universitas Brawijaya Malang, Indonesia
[email protected]
Eriq M. Adams J.1, Satrio A. Wicaksono2 Program Teknologi Informasi dan Ilmu Komputer Universitas Brawijaya Malang, Indonesia 1
[email protected],
[email protected]
Abstrak – Kampus merupakan tempat dimana sebuah layanan sistem informasi web pencarian rute terpendek antar gedung sangat dibutuhkan untuk menemukan lokasi gedung yang tersebar di berbagai penjuru kampus. Ada beberapa rute yang bisa ditempuh untuk menuju ke suatu gedung. Masyarakat menginginkan jalur yang efisien sehingga dapat menghemat waktu. Algoritma Floydwarshall merupakan salah satu algoritma untuk menyelesaikan masalah ini. Paper ini menjelaskan aplikasi web pencarian rute terpendek antar gedung di kampus yang memiliki fitur mencari suatu lokasi gedung serta jarak terpendek yang dapat dilalui. Hasil pengujian menunjukkan bahwa keseluruhan fungsional bekerja dengan baik, dengan akurasi 100%.
setiap sisi berhubungan dengan satu atau dua buah simpul[3]. Salah satu masalah umum yang dapat diselesaikan dengan menggunakan teori graf yaitu masalah rute terpendek (Shortest Path Problem) yang mencari rute dengan jumlah bobot paling minimum [1]. Algoritma Floyd-warshall merupakan salah satu algoritma untuk menyelesaikan masalah ini [2]. Oleh karena itu dibutuhkan sebuah sistem informasi web pencarian rute terpendek antar gedung di kampus yang dapat memudahkan masyarakat dalam mencari sebuah fakultas atau jurusan tertentu dan jalur yang dapat dilalui untuk menuju fakultas atau jurusan tersebut. METODE PENELITIAN Operasi dasar dalam aplikasi web pencarian rute terpendek ini adalah mendapatkan rute terpendek antar gedung di kampus dan menampilkan visualisasi peta. Arsitektur sistem menjelaskan mekanisme kerja aplikasi web pencarian rute terpendek ini. Gambar 1 menunjukkan perancangan arsitektur sistem dari aplikasi ini. Algoritma Floyd-Warshall adalah salah satu varian dari pemrograman dinamis, yaitu suatu metode yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait [04]. II.
Kata kunci: rute terpendek, algoritma Floyd-warshall, PHP, kampus. I. PENDAHULUAN Sistem informasi semakin dibutuhkan oleh banyak pihak, informasi tersebut diperlukan pengguna untuk berbagai keperluan [1]. Lingkungan kampus merupakan salah satu tempat dimana sebuah layanan sistem informasi sangat dibutuhkan baik untuk mahasiswa, karyawan, maupun masyarakat luas. Sistem informasi yang ada pada kampus diharapkan juga harus dapat membantu aktivitas di kampus untuk menemukan lokasi jurusan atau fakultas yang dibutuhkan. Dalam sebuah kampus terdapat gedung fakultas atau jurusan yang letaknya relatif terpisah satu dengan yang lain. Setiap fakultas atau jurusan terhubung dengan fasilitas jalan raya kampus, yang juga merupakan sarana untuk mengakses antara satu gedung dengan gedung lainnya. Secara matematis kondisi seperti ini dapat direpresentasikan sebagai sebuah graf. Graf adalah pasangan himpunan vertex/simpul dan edges/sisi, dimana
k
d ij
min d ij
k 1
, d ik
k 1
d kj
k 1
jika k 1
Algoritma ini bekerja dengan menghitung shortestPath(i,j,1) untuk semua pasangan (i,j), kemudian hasil tersebut akan digunakan untuk menghitung shortestPath(i,j,2) untuk semua pasangan (i,j), dst. [7]. Proses ini akan terus berlangsung hingga k = n dan kita telah menemukan jalur terpendek untuk semua pasangan (i,j) menggunakan simpul-simpul perantara [4]. 30
Journal Basic Science And Technology, 1(2), 30-34,2012 ISSN : 2089-8185
Gambar 1 Perancangan arsitektur sistem -
Gambar 4 Relasi antar class
Gambar 2 Proses pencarian rute pada sistem
Proses pencarian rute pada sistem aplikasi web pencarian rute terpendek ditunjukan pada Gambar 2. Aplikasi web pencarian rute terpendek antar gedung di kampus memiliki beberapa kebutuhan fungsional yang dimodelkan dalam diagram use case, Diagram use case aplikasi ini dibagi menjadi dua, yaitu diagram use case user dan diagram use case administrator. Gambar 3 menggambarkan diagram use case sistem. Aplikasi ini dibangun oleh sejumlah class yang saling membentuk relasi. Class diagram memberikan gambaran pemodelan elemen-elemen class serta fungsi dan relasinya dengan class lain dalam sebuah sistem. Terdapat enam class pada aplikasi ini yaitu class peta, node_jarak, hubungi, modul, gedung, dan user. Relasi antar class pada perancangan perangkat lunak ini ditunjukkan pada Gambar 4, sedangkan diagram class sistem ini ditunjukkan pada Gambar 5,
Gambar 5 Diagram class sistem
III. HASIL DAN PEMBAHASAN Aplikasi web pencarian rute terpendek antar gedung ini mempunyai beberapa proses (method) utama, yang terbagi dalam beberapa class. Dalam makalah ini hanya akan disebutkan salah satu algoritma saja sehingga tidak semua method akan dicantumkan. Implementasi algoritma ini akan direpresentasikan dalam bentuk pseudocode. Gambar 6 menggambarkan pseudocode algoritma untuk mendapatkan rute terpendek. NAMA ALGORITMA: getDistance DEKLARASI String → nodeAwal, nodeAkhir Integer → jarak DESKRIPSI Masukan : nodeAwal, nodeAkhir Proses : 1. Menginisialisasi variabel $awal = $_POST dan $akhir = $_POST merupakan node awal dan node akhir 2. Memberi nilai atribut nodeAwal dan nodeAkhir 3. Memanggil variabel $fw sebagai new FloydWarshall ($graph, $nodes) 4. Mencetak variabel $fw>get_distance Keluaran:Sistem menampilkan jarak dari titik awal menuju titik akhir
Gambar 6 Pseudocode algoritma getDistance Gambar 3 Giagram use case sistem
Pemodelan ke dalam flow graph yang telah dilakukan terhadap algoritma getDistance menghasilkan jumlah 31
Journal Basic Science And Technology, 1(2), 30-34,2012 ISSN : 2089-8185 Gambar 7 Tampilan menu user
kompleksitas siklomatis (cyclomatic complexity) melalui persamaan V(G) = E – N + 2. V(G) = E – N + 2 =0–1+2 =1 Berdasarkan dari nilai cyclomatic complexity yang telah didapatkan dari perhitungan maka ditentukan satu buah basis set dari jalur independent, yaitu : Jalur 1 : 1 Penentuan kasus uji untuk jalur independent tersebut dan hasil eksekusinya dijelaskan pada Tabel 5.1. Tabel 1 Kasus uji untuk pengujian unit algoritma getDistance Jalur Kasus Uji Hasil yang didapatkan Menjalankan Mendapatkan jarak ter1 operasi pendek dari titik awal ke get_distance titik akhir
Gambar 8 Tampilan menu administrator
Tabel 2 Pengujian validasi sistem
No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Antarmuka aplikasi web pencarian rute terpendek antar gedung di kampus ini terdiri dari dua buah menu khusus administrator dan user biasa. Administrator mempunyai hak akses lebih dibandingkan user, yaitu dapat melakukan proses tambah, hapus, dan edit data. Implementasi antarmuka aplikasi dilakukan dengan komponen graphical user interface dari web browser dengan format php (*.php). Gambar 7 menunjukkan implementasi antarmuka aplikasi pada menu user. Sedangkan tampilan menu administrator dapat ditunjukkan dengan gambar 8 setelah administrator sukses melakukan login. Pengujian validasi dilakukan dengan objek uji kebutuhan fungsional dari perangkat lunak Web Pencarian Rute Terpendek. Pengujian validasi dilakukan dengan teknik black-box testing [5] yaitu dengan melakukan pengujian terhadap kinerja seluruh sistem. Kasus uji untuk pengujian validasi dapat dilihat pada Tabel 2.
Nama Kasus Uji Melihat info jurusan. Mencari rute terpendek. Mengirim pesan. Login. Logout. Tambah akun. Edit akun. Hapus akun. Tambah modul. Edit modul. Hapus modul. Tambah rute. Hapus rute. Edit rute. Hapus rute. Tambah gedung. Edit gedung. Hapus gedung. Tambah peta. Edit peta. Hapus peta. Balas Pesan. Hapus pesan. Tambah informasi jurusan.
Status Validitas Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid Valid
Akurasi algoritma Floyd-warshall terhadap sistem dapat diketahui dengan melakukan pengujian akurasi [04]. Data yang diuji berjumlah 10 data. Prosedur pengujiannya adalah memasukkan titik awal dan titik akhir, kemudian sistem menghasilkan hasil prediksi. Hasil prediksi tersebut dicocokkan kesesuaiannya dengan perhitungan manual.
32
Journal Basic Science And Technology, 1(2), 30-34,2012 ISSN : 2089-8185 Perhitungan untuk pengujian akurasi dapat dijabarkan dengan accuracy sebagai berikut[6]: 𝑎𝑐𝑐𝑢𝑟𝑎𝑐𝑦 =
Jalur1 : Jalur hasil perhitungan sistem Jalur2 : Jalur hasil perhitungan manual
𝑁𝑐
𝑎𝑐𝑐𝑢𝑟𝑎𝑐𝑦 =
𝑁
Dimana: Nc : Number of positive instances covered by rule. N : Number of instances covered by rule
10
= 10
IV. KESIMPULAN DAN SARAN Berdasarkan hasil perancangan dan pengujian yang dilakukan, maka diambil kesimpulan dan saran sebagai berikut: 1. Perancangan aplikasi web pencarian rute terpendek ini menggunakan bahasa pemodelan UML dan diimplementas ikan menggunakan bahasa pemrograman PHP dan MySql. Untuk objek peta yang berisikan gambar dan visualisasi rute menggunakan Adobe Flash dengan format *.swf. 2. Aplikasi web Pencarian Rute Terpendek dapat digunakan untuk mencari informasi gedung dan mencari rute terpendek antar gedung di kampus. 3. Hasil pengujian whitebox dan pengujian blackbox pada perangkat lunak aplikasi web pencarian rute terpendek telah valid hal ini telah dibuktikan dengan dilakukan proses pengujian unit, pengujian integrasi, dan pengujian validasi. 4. Berdasarkan hasil pengujian, tingkat akurasi algoritma Floyd-warshall selalu menunjukkan nilai 100%. 5. Aplikasi web pencarian rute terpendek antar gedung di kampus dapat dikembangkan menjadi SOA (Service Oriented Architecture) agar gapat dikembangkan oleh pihak ke tiga. 6. Aplikasi web pencarian rute terpendek antar gedung di kampus dapat dikembangkan dengan dibuat versi mobile sehingga lebih praktis dalam penggunaannya bagi pengunjung. 7. Visualisasi rute peta kampus dapat dikembangkan menjadi animasi dengan format 3D (tiga dimensi).
2
150 70 3
70 130
4
160
5
253 384
320
= 100%
Berdasarkan hasil pengujian akurasi dengan 10 data dihasilkan akurasi sebesar 100 %.
Pengujian dilakukan terhadap sebagian gedung yang terdapat pada kampus. Gambar 9 menggambarkan letak sebagian gedung yang terdapat pada kampus.
1
𝑁𝑐 𝑁
6
Gambar 9 Sebagian node gedung kampus
Hasil pengujian akurasi dari 10 data yang diuji adalah sebagai berikut: Tabel 3 Hasil Pengujian Akurasi No Awal Akhir Jalur1 Jalur2 Hasil 2 4 2-1-4 2-1-4 P 1 2 3 2-1-4-3 2-1-4-3 P 2 3 1 3-4-5-2- 3-4-5-2P 3 1 1 6 5 6-4-5 6-4-5 P 4 6 3 6-3 6-3 P 5 4 6 4-3-6 4-3-6 P 6 1 6 1-4-3-6 1-4-3-6 P 7 3 5 3-4-5 3-4-5 P 8 6 2 6-4-5-2 6-4-5-2 P 9 2 6 2-5-6 2-5-6 P 10
V. DAFTAR PUSTAKA Erawati Dewi, Luh. 2010. Pencarian Rute Terpendek Tempat Wisata Bali Menggunakan Algoritma Dijkstra. Jurnal Fakultas Teknik Informatika Universitas Pendidikan Ganesha. Bali. [2] Pandey, H. M. 2008. Design Analysis and Algorithms. University Science Press. New Delhi.
Keterangan: 1 : Gedung Widyaloka 2 : Gedung Fakultas THP 3 : Gedung Jurusan Fisika 4 : Gedung Fakultas Ilmu Bahasa 5 : Gedung Perpustakaan 6 : Gedung Gazebo
[1]
33
Journal Basic Science And Technology, 1(2), 30-34,2012 ISSN : 2089-8185 [3]
[4]
[5]
[6]
[7]
Leon, Steven J. 2001. Aljabar Linear dan Aplikasinya, Edisi Kelima. Penerbit Erlangga. Jakarta. Cormen, Thomas H. 2003. Introduction to Algorithms 2nd Edition. The MIT Press. Cambridge, London. Pressman, Roger S. 2001. Software Engineering : A Practitioner’s Approach, Fifth Edition. McGraw Hill. Pang-Ning Tan, Michael Steinbach, Vipin Kumar. 2006. Introduction to Data Mining. Addison-Wesley Company. United States. Prabakhar Gupta, Vineet Agarwal. 2010. Design and Analysis of Algorithms. Asoke K. Gosh Learning Private Limited. New Delhi
34
