perbandingan penggunaan algoritma dijkstra jalur terpendek ... · pdf fileperbandingan...

PERBANDINGAN PENGGUNAAN ALGORITMA DIJKSTRA

DAN ALGORITMA FLOYD-WARSHALL UNTUK PENCARIAN

JALUR TERPENDEK PADA BUS TRANS JOGJA

Skripsi

Diajukan Untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Komputer

Program Studi Teknik Informatika

Oleh:

Agustinus Wikrama Darmadipta

095314053

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2013

i

SYST

OOLS

DEM

O

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

SKRIPSI

PERBANDINGAN PENGGUNAAN ALGORITMA DIJKSTRA

DAN ALGORITMA FLOYD-WARSHALL UNTUK PENCARIAN

JALUR TERPENDEK PADA BUS TRANS JOGJA

Oleh:

Agustinus Wikrama Darmadipta

NIM: 095314053

Telah disetujui oleh:

Dosen Pembimbing Tugas Akhir

Sri Hartati Wijono, S.Si., M. Kom. Tanggal:

ii

SYST

OOLS

DEM

O

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

LEMBAR MOTTO

The dreams cannot come to you.

The only one who can make the distance between you and your dreams

getting closer is yourself.

SO GO CHASE IT!

iv

SYST

OOLS

DEM

O

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PUBLIKASI KARYA ILMIAH UNTUK KEPERLUAN AKADEMIS

Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma:

Nama : Agustinus Wikrama Darmadipta

Nomor Mahasiswa : 095314053

Demi mengembangkan ilmu pengetahuan, saya memberikan kepada perpustakaan

Universitas Sanata Dharma karya ilmiah saya yang berjudul:

PERBANDINGAN PENGGUNAAN ALGORITMA DIJKSTRA DAN

ALGORITMA FLOYD-WARSHALL UNTUK PENCARIAN JALUR

TERPENDEK PADA BUS TRANS JOGJA

Beserta perangkat yang diperlukan. Dengan demikian saya memberikan kepada

Perpustakaan Universitas Sanata Dharma hak untuk menyimpan, mengalihkan dalam

bentuk media lain, mengelolanya dalam bentuk pangkalan data, mendistribusikan

secara terbatas, dan mempublikasikannya di Internet atau media lain untuk

kepentingan akademis tanpa perlu meminta izin dari saya maupun memberikan

royalti kepada saya selama tetap mencantumkan nama saya sebagai penulis.

Demikian pernyataan ini saya buat dengan sebenarnya.

Yogyakarta, 22 Agustus 2013

Agustinus Wikrama Darmadipta

vi

SYST

OOLS

DEM

O

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ABSTRACT

The confusing about how to decide what trayek someone must take in the case

of Bus Trans Jogja has became a problem for the user that want to go to a destination

from the source that he wanted in Yogyakarta. That problem made the writer want to

solve it by making an Android based mobile application that can give an advice to the

user of Bus Trans Jogja about the trayek that he must take to get to a destination by

the shortest path .

The shortest path is calculated using two shortest path algorithms, Dijkstra

and Floyd-Warshall algorithm. Dijkstra algorithm, using greedy as its method, on the

other way Floyd-Warshall algorithm using dynamic programming as it method. The

reason why using those two algorithm is because this research want to know which

algorithm that more optimal to be implemented in the case of the shortest path search

in the route of Bus Trans Jogja.

Comparisons that be used to decide the optimal algorithm are complexity of

asimptotik time and the running time of each algorithm. The validity that have given

by each algorithm is also a thing that decide the optimality of each algorithm.

viii

SYST

OOLS

DEM

O

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

tidak menyerah dan selalu bersemangat untuk menyelesaikan tugas

akhir ini dengan baik dan tepat waktu.

5. Fransiskus Ageng Widodo dan Audris Evan Utomo, selaku teman

penulis yang telah membantu dalam menyelesaikan permasalahan

coding yang penulis alami sewaktu pembuatan aplikasi.

6. Ardha, Eki, Aden, Yosi, Surya, dan Fidi yang selalu menghibur

penulis dalam menyelesaikan tugas akhir ini sehingga penulis dapat

selalu ceria ketika mengerjakan tugas akhir bersama-sama di

laboratorium komputer basis data.

Yogyakarta, 22 Agustus 2013

Agustinus Wikrama Darmadipta

Penulis

x

SYST

OOLS

DEM

O

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

3.4. Diagram Aktivitas .................................................................................. 51

3.4.1. Diagram Aktivitas Menentukan Titik Awal .................................... 52

3.4.2. Diagram Aktivitas Menentukan Titik Tujuan ................................. 52

3.4.3. Diagram Aktivitas Mencari Halte ................................................... 53

3.4.4. Diagram Aktivitas Melihat Jalur Bus yang Ditempuh, Melihat Nilai

Jarak yang Ditempuh, Melihat Saran Trayek Bus yang Harus Dipilih, dan

Melihat Running Time Algoritma ................................................................. 54

3.4.5. Diagram Aktivitas Melihat Help ..................................................... 55

3.5. Diagram Sekuensial ................................................................................ 55

3.5.1. Diagram Sekuensial Menentukan Titik Awal ................................. 55

3.5.2. Diagram Sekuensial Menentukan Titik Tujuan .............................. 56

3.5.3. Diagram Sekuensial Mencari Halte ................................................ 56

3.5.4. Diagram Sekuensial Melihat Jalur Bus yang Ditempuh, Melihat

Nilai Jarak yang Ditempuh, Melihat Saran Trayek Bus yang Harus Dipilih,

dan Melihat Running Time Algoritma ........................................................... 57

3.5.5. Diagram Sekuensial Melihat Help .................................................. 58

3.6. Diagram Kelas ........................................................................................ 59

3.7. Kelas Analisis ......................................................................................... 60

3.8. Operasi dan Atribut Tiap Kelas .............................................................. 63

3.9. Cara Pengujian........................................................................................ 72

3.10. Skenario Pengujian ............................................................................. 73

3.11. Desain Antarmuka .............................................................................. 78

3.11.1. Desain Antarmuka Tampilan Awal ................................................. 79

3.11.2. Desain Antarmuka Jalur Terpendek Telah Ditemukan ................... 79

3.11.3. Desain Antarmuka Tampilan Details .............................................. 80

BAB IV : IMPLEMENTASI ............................................................................... 81

4.1. Spesifikasi Perangkat Keras dan Lunak ................................................. 81

4.2. Pengolahan Data ..................................................................................... 82

4.3. Implementasi Kelas Graph ..................................................................... 83

4.3.1. Implementasi Metode Greedy dengan Algoritma Dijkstra ............. 84

xii

SYST

OOLS

DEM

O

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Lampiran 8: Source Code Kelas TemporaryJalur_n_Jarak ............................. 154

Lampiran 9: Source Code Kelas PathOverlay ................................................. 155

Lampiran 10: Source Code Kelas SitesOverlay .............................................. 156

Lampiran 11: Source Code Kelas Help ........................................................... 166

Lampiran 12: Source Code Kelas MainActivity ............................................. 166

Lampiran 13: Source Code Kelas Map ........................................................... 168

xiv

SYST

OOLS

DEM

O

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Gambar 4.1 Gambar Source Code untuk Algoritma Dijkstra ............................. 87

Gambar 4.2 Gambar Source Code untuk Algoritma Floyd-Warshall ................. 89

Gambar 4.3 Gambar Source Code untuk Perpindahan Bus ................................ 92

Gambar 4.4 Gambar Source Code untuk Penghitungan Running Time Algoritma

............................................................................................................................... 93

Gambar 4.5 Tampilan Halaman Menu ................................................................ 94

Gambar 4.6 Title.xml .......................................................................................... 95

Gambar 4.7