IMPLEMENTASI ALGORITMA FLOYD-WARSHALL UNTUK PENENTUAN RUTE TERPENDEK MENUJU WAHANA BERMAIN (STUDI KASUS JAWA TIMUR PARK 1 KOTA BATU)
TUGAS AKHIR Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Oleh: DEO SANDA PRATAMA PUTRA NIM. 09560376
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2013
LEMBAR PERSETUJUAN
IMPLEMENTASI ALGORITMA FLOYD-WARSHALL UNTUK PENENTUAN RUTE TERPENDEK MENUJU WAHANA BERMAIN (STUDI KASUS JAWA TIMUR PARK 1 KOTA BATU)
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata1 Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui, Pembimbing I
Pembimbing II
Ir. NUR ALIF MARDIYAH, MT NIP. 108.9203.0257
YUFIS AZHAR, S.Kom NIDN. 0728088701
LEMBAR PENGESAHAN
IMPLEMENTASI ALGORITMA FLOYD-WARSHALL UNTUK PENENTUAN RUTE TERPENDEK MENUJU WAHANA BERMAIN (STUDI KASUS JAWA TIMUR PARK 1 KOTA BATU)
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata1 Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh: DEO SANDA PRATAMA PUTRA NIM. 09560376
Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal 26 Juli 2013
Menyetujui, Penguji I
Penguji II
EKO BUDI CAHYONO, S.Kom, M.T NIP. 10895040330
SOFYAN ARIFIANTO, S.Si, M.Kom
Mengetahui, Ketua Jurusan Teknik Informatika
EKO BUDI CAHYONO, S.Kom, M.T NIP. 10895040330
LEMBAR PERNYATAAN KEASLIAN Yang bertanda tangan dibawah ini: NAMA
: DEO SANDA PRATAMA PUTRA
NIM
: 09560376
FAK. / JUR. : TEKNIK / INFORMATIKA
Dengan
ini
saya
“IMPLEMENTASI
menyatakan
bahwa
ALGORITMA
Tugas
Akhir
dengan
FLOYD-WARSHALL
judul
UNTUK
PENENTUAN RUTE TERPENDEK MENUJU WAHANA BERMAIN (STUDI KASUS JAWA TIMUR PARK 1 KOTA BATU)” beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain, baik sebagian maupun seluruhnya, kecuali dalam bentuk kutipan yang telah disebutkan sumbernya. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya. Apabila kemudian ditemukan adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada klaim dari pihak lain terhadap keaslian karya saya ini maka saya siap menanggung segala bentuk resiko/sanksi yang berlaku. Malang, 18 Juli 2013 Yang Membuat Pernyataan
DEO SANDA PRATAMA PUTRA
Mengetahui, Pembimbing I
Pembimbing II
Ir. NUR ALIF MARDIYAH, MT NIP. 108.9203.0257
YUFIS AZHAR, S.Kom NIDN. 0728088701
KATA PENGANTAR Puji syukur kehadirat Allah SWT yang telah memberikan kekuatan, petunjuk serta melimpahkan rahmat dan hidayah-Nya, sehinggan penulis bisa menyelesaikan Tugas Akhir yang berjudul: "IMPLEMENTASI ALGORITMA FLOYD-WARSHALL UNTUK PENENTUAN RUTE TERPENDEK MENUJU WAHANA BERMAIN (STUDI KASUS JAWA TIMUR PARK 1 KOTA BATU)" Di dalam laporan ini disajikan pokok-pokok bahasan yang meliputi pengimplementasian algoritma Floyd Warshall kedalam sistem penentuan rute terpendek menuju wahana bermain dan aplikasi counter pengunjung agar pengguna bisa mengetahui jumlah antrian dalam wahana tertentu. Penulis menyadari bahwa dalam penulisan tugas akhir ini masih banyak kekurangan dan keterbatasan. Oleh karena itu segala saran yang membangun untuk kesempurnaan tulisan ini sangat penulis harapkan. Akhir kata penulis berharap semoga Tugas Akhir ini dapat bermanfaat dan menjadi tambahan ilmu pengetahuan.
Malang, 18 Juli 2013
Penulis
DAFTAR ISI Lembar Persetujuan Lembar Pengesahan Lembar Pernyataan Abstraksi ............................................................................................................ iv Abstract ............................................................................................................... v Lembar Persembahan .......................................................................................... vi Kata Pengantar ................................................................................................... vii Daftar Isi............................................................................................................. vi Daftar Gambar .................................................................................................... ix Daftar Tabel........................................................................................................ xi BAB I PENDAHULUAN .................................................................................... 1 1.1 1.2 1.3 1.4 1.5 1.6
Latar Belakang....................................................................................... 1 Rumusan Masalah.................................................................................. 2 Tujuan ................................................................................................... 2 Batasan Masalah .................................................................................... 2 Metodologi ............................................................................................ 3 Sistematika Penulisan ............................................................................ 5
BAB II LANDASAN TEORI .............................................................................. 6 2.1 Konsep Dasar Algoritma ........................................................................ 6 2.1.1 Sejarah Algoritma .............................................................................. 6 2.1.2 Definisi Algoritma ............................................................................ 6 2.2 Konsep Graf .......................................................................................... 7 2.2.1 Sejarah Graf ....................................................................................... 7 2.2.2 Definisi Graf .................................................................................... 7 2.2.3 Graf Berarah ...................................................................................... 8 2.2.4 Graf tak Berarah ............................................................................... 8 2.2.5 Graf Berbobot .................................................................................... 9 2.2.6 Representasi Graf ............................................................................. 9 2.3 Definisi Lintasan (Path) ....................................................................... 10 2.3.1 Lintasan Terpendek (Shortest Path) .................................................. 10 2.4 Algoritma Floyd-Warshall ................................................................... 11 2.4.1 Keunggulan Algoritma Floyd-Warshall ............................................ 13 2.4.2 Studi Literatur Algoritma Floyd-Warshall ........................................ 13 2.4.3 Karakteristik Pemrograman Dinamis ................................................ 14 2.5 Mobile Application .............................................................................. 15
BAB III ANALISA DAN PERANCANGAN SISTEM ...................................... 17 3.1 Analisa Data ........................................................................................ 17 3.2 Analisa Algoritma ................................................................................ 22 3.2.1 Analisa Algoritma Floyd Warshall ................................................... 22 3.2.2 Pseudocode Algoritma Floyd-Warshall ............................................ 24 3.3 Analisa Sistem ..................................................................................... 25 3.3.1 Spesifikasi Perangkat Lunak ............................................................. 25 3.3.2 Perancangan Alur Proses Sistem....................................................... 25 3.3.3 Use Case Diagram ............................................................................ 26 3.3.4 Activity Diagram.............................................................................. 27 3.4 Perancangan Sistem ............................................................................. 30 3.4.1 Desain Database .................................................................................. 30 3.4.2 Sequence Diagram ........................................................................... 30 3.4.3 Class Diagram .................................................................................. 32 3.4.4 Perancangan User Interface .............................................................. 33 BAB IV IMPLEMENTASI DAN HASIL PENGUJIAN .................................... 36 4.1 Spesifikasi Kebutuhan Hardware dan Software .................................... 36 4.1.1 Kebutuhan Hardware ........................................................................... 36 4.1.2 Kebutuhan Software ......................................................................... 37 4.2 Implementasi Sistem ............................................................................ 37 4.2.1. Pembuatan Basis Data .................................................................. 38 4.2.2. Pembuatan Fungsi Koneksi Database ............................................ 38 4.3 Implementasi Kode Program ................................................................ 39 4.3.1 Implementasi Kode pada Aplikasi Counter Pengunjung ................... 39 4.3.1.1 Form Login ............................................................................... 39 4.3.1.2 Interface Halaman Counter ........................................................ 41 4.3.1.3 Reset Jumlah Antrian ................................................................ 43 4.3.1.4 Log out ..................................................................................... 44 4.3.2 Implementasi Kode pada Aplikasi Penentuan Rute Terpendek.......... 45 4.3.2.1 Pilih Wahana ............................................................................. 45 4.3.2.2 Melihat Keterangan Wahana ..................................................... 47 4.3.2.3 Peta(map) .................................................................................. 48 4.3.2.4 Rute Menuju Wahana ................................................................ 51 4.3.3 Implementasi Algoritma Floyd-Warshall .......................................... 52 4.4 Pengujian ............................................................................................. 52 4.4.1 Pengujian Sistem .............................................................................. 54 4.4.1.1 Pengujian UCC-01 (Update Counter Antrian) ........................... 54 4.4.1.2 Pengujian UCP-01 (Melihat Rute) ............................................. 55 4.4.1.3 Pengujian UCP-02 (Melihat Keterangan Wahana) ..................... 57 4.4.2 Pengujian Algoritma Floyd-Warshall ............................................... 57 4.5 Evaluasi ............................................................................................... 61
4.5.1 Evaluasi Fungsionalitas .................................................................... 61 4.5.2 Evaluasi Algoritma Floyd-Warshall.................................................. 62 BAB V KESIMPULAN DAN SARAN.............................................................. 64 5.1 5.2
Kesimpulan.......................................................................................... 64 Saran ................................................................................................... 64
DAFTAR PUSTAKA ........................................................................................ 65 LAMPIRAN ...................................................................................................... 67
DAFTAR GAMBAR Gambar 1. 1 Implementasi sistem ........................................................................ 4 Gambar 2. 1 Jembatan Konigsberg (ROS99) ........................................................ 7 Gambar 2. 2 (a) graf sederhana, (b)graf ganda, (c)graf semu ................................ 8 Gambar 2. 3 Graf Berarah .................................................................................... 8 Gambar 2. 4 Graf tak Berarah .............................................................................. 9 Gambar 2. 5 Graf Berbobot .................................................................................. 9 Gambar 2. 6 Contoh Graf ................................................................................... 12 Gambar 3. 1 Peta rute Jawa Timur Park 1 .......................................................... 18 Gambar 3. 2 Flowchart Algoritma Floyd-Warshall ............................................. 22 Gambar 3. 3 Contoh graf sederhana dan bobotnya.............................................. 23 Gambar 3. 4 Hasil dari Algoritma Floyd-Warshall ............................................. 24 Gambar 3. 5 Flowcart Aplikasi .......................................................................... 26 Gambar 3. 6 Use Case Diagram Aplikasi Penentuan Rute .................................. 27 Gambar 3. 7 Use Case Diagram Aplikasi Counter .............................................. 27 Gambar 3. 8 Activity Diagram Aplikasi Penentuan Rute .................................... 28 Gambar 3. 9 Activity Diagram Aplikasi Counter ................................................ 29 Gambar 3. 10 Entity Relationship Diagram ........................................................ 29 Gambar 3. 11 Sequence Diagram Aplikasi Penentuan Rute ................................ 30 Gambar 3. 12 Sequence Diagram Aplikasi Counter ............................................ 32 Gambar 3. 13 Class Diagram Aplikasi ............................................................... 33 Gambar 3. 14 Rancangan Form Login ................................................................ 34 Gambar 3. 15 Rancangan Interface Aplikasi Counter ......................................... 34 Gambar 3. 16 Rancangan User Interface Aplikasi Penentuan Rute ..................... 35 Gambar 4. 1 Tabel MySQL ................................................................................ 38 Gambar 4. 2 Kode Program Koneksi ke Database .............................................. 39 Gambar 4. 3 Form Login Aplikasi Counter ....................................................... 39 Gambar 4. 4 Potongan Kode Proses Login pada sisi Client ................................ 40 Gambar 4. 5 Potongan Kode Proses Login pada sisi Server ................................ 40 Gambar 4. 6 Tabel pada Database untuk Login .................................................. 41 Gambar 4. 7 Interface Aplikasi Counter ............................................................. 41 Gambar 4. 8 Fungsi Counter pada sisi Client ...................................................... 42
Gambar 4. 9 Potongan Kode Counter pada sisi Server ........................................ 43 Gambar 4. 10 Tampilan Jika Mereset Jumlah Antrian ........................................ 43 Gambar 4. 11 Kode Program untuk Reset yang ada pada Server......................... 44 Gambar 4. 12 Konfirmasi untuk logout .............................................................. 44 Gambar 4. 13 Kode Program untuk logout yang ada pada Server ....................... 45 Gambar 4. 14 Interface Pilih Wahana ................................................................. 45 Gambar 4. 15 Fungsi List Nama Wahana pada sisi Client .................................. 46 Gambar 4. 16 Potongan Kode untuk Mendapatkan Data pada Database ............. 46 Gambar 4. 17 Interface Halaman Keterangan Wahana........................................ 47 Gambar 4. 18 Popup gambar .............................................................................. 48 Gambar 4. 19 Peta dan Nama Wahana ............................................................... 49 Gambar 4. 20 Daftar Nama Wahana beserta Antrian .......................................... 50 Gambar 4. 21 Fungsi untuk Mengambil Checkedbox yang telah dipilih ............. 50 Gambar 4. 22 Potongan Kode untuk Menampilkan Daftar Nama Wahana yang telah Dipilih beserta Antriannya ......................................................................... 51 Gambar 4. 23 Interface Rute Menuju Wahana Bermain ...................................... 52 Gambar 4. 24 Potongan Kode Algoritma Floyd-Warshall................................... 53 Gambar 4. 25 Penentuan Rute Melalui Aplikasi Pintu Masuk ke Wahana Bermain Midi Skater ........................................................................................................ 58 Gambar 4. 26 Graf Penentuan Rute dari Pintu Masuk menuju Midi Skater ......... 58 Gambar 4. 27 Matriks Hubungan Jalur dari Pintu Masuk menuju Midi Skater .... 59 Gambar 4. 28 Evaluasi Pengujian Aplikasi Penenuan Rute pada device Android 61
DAFTAR TABEL Tabel 3. 1 Data wahana bermain ........................................................................ 17 Tabel 3. 2 Nilai Jarak Antar Titik ....................................................................... 19 Tabel 4. 1 Daftar Use Case Aplikasi Counter ..................................................... 54 Tabel 4. 2 Daftar Use Case Aplikasi Penentuan Rute ......................................... 54 Tabel 4. 3 Pengujian UCC-01 ............................................................................ 54 Tabel 4. 4 Pengujian UCP-01 ............................................................................. 55 Tabel 4. 5 Pengujian UCP-02 ............................................................................. 57 Tabel 4. 6 Pengujian pada 15 Device Android .................................................... 62 Tabel 4. 7 Perbandingan Pencarian Rute Aplikasi dan Perhitungan Manual........ 62
DAFTAR PUSTAKA
[1] Algoritma Floyd-Warshall. 2012. http://id.wikipedia.org/wiki/Algoritma_Floyd-Warshall. diakses pada 8 April 2013 [2] Diaz Novandi, Raden Aprian. 2011. Perbandingan Algoritma Dijkstra dan Algoritma Floyd-Warshall dalam Penentuan Lintasan Terpendek (Single Pair Shortest Path). Program Studi Teknik Informatika, Sekolah Teknik Elektro dan Informatika ITB. Bandung. [3] Fanani, Lutfi. 2012. Rancang Bangun Aplikasi Web Pencarian Rute Terpendek Antar Gedung di Kampus Menggunakan Algoritma Floydwarshall. Program Teknologi Informasi dan Ilmu Komputer Universitas Brawijaya. Malang [4] Gunawan, Cahya 2012. Pencarian Rute Terpendek Menggunakan Algoritma Greedy (Simulasi Rute Angkot Cicaheum Ciroyom). Sistem Informasi. Universitas Komputer Indonesia. Bandung. [5] Handaka, M.S. 2010. Perbandingan Algoritma Djikstra (Greedy), Bellman-Ford (BFS-DFS), dan Floyd-Warshall (Dynamic Programming) dalam Pengaplikasian Lintasan Terpendek pada Link-State Routing Protocol. Bandung. ITB. [6] Hidayat, Andri. 2013. Pencarian Rute Terpendek dengan Menggunakan Algoritma Floyd-Warshall untuk Taksi dengan Rute Terminal Leuwi Panjang - Dipati Ukur. Sistem Informasi. Universitas Komputer Indonesia. Bandung. [7] Iftadi, Irwan; Jauhari, Wakhid Ahmad; Nugroho, Beny. 2011. Perancangan Peta Evakuasi Menggunakan Algoritma Floyd Warshall untuk Penentuan Lintasan: Studi Kasus. Teknik Industri, Universitas Sebelas Maret. Semarang. [8] Jawa Timur Park 1. 2011. http://jawatimurpark1.com/wahana.php, diakses pada 1 Juli 2013. [9] Jquery Mobile. 2013. http://view.jquerymobile.com/1.3.1/dist/demos/, diakses pada 5 Juni 2013
[10] Konsep dasar teori graf. 2013. http://www.scribd.com/doc/93190847/Konsep-Dasar-Teori-Graf, diakses pada 21 Mei 2013 [11] Phonegap.2013. http://docs.phonegap.com/en/2.9.0/cordova_storage_storage.md.html#Stor age, diakses pada 3 Juni 2013 [12] Ramadiyan, Deasy. Aplikasi Representasi Graf. Teknik Informatika. Institute Teknologi Bandung. Bandung. [13] Saputra, Ragil. 2011. Sistem Informasi Geografis Pencarian Rute Optimum Obyek Wisata Kota Yogyakarta Dengan Algoritma FloydWarshall. Program Studi Teknik Informatika FMIPA UNDIP. Semarang. [14] Sejarah lahirnya Teori Graph. 2011. http://www.scribd.com/doc/51801211/SEJARAH-LAHIRNYA-TEORIGRAPH, diakses pada 21 Mei 2013.
