PERBANDINGAN PENGGUNAAN ALGORITMA DIJKSTRA DAN ALGORITMA FLOYD-WARSHALL UNTUK PENCARIAN JALUR TERPENDEK PADA BUS TRANS JOGJA

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PERBANDINGAN PENGGUNAAN ALGORITMA DIJKSTRA DAN ALGORITMA FLOYD-WARSHALL UNTUK PENCARIAN

Skripsi

EM O

JALUR TERPENDEK PADA BUS TRANS JOGJA

Diajukan Untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Komputer

O

LS

D

Program Studi Teknik Informatika

Oleh:

Agustinus Wikrama Darmadipta

O

095314053

SY

ST

PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2013

i



SKRIPSI

EM O

PERBANDINGAN PENGGUNAAN ALGORITMA DIJKSTRA

DAN ALGORITMA FLOYD-WARSHALL UNTUK PENCARIAN JALUR TERPENDEK PADA BUS TRANS JOGJA

Oleh:

D


LS

NIM: 095314053

O

O

Telah disetujui oleh:

SY

ST

Dosen Pembimbing Tugas Akhir

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

Tanggal: ………………

ii



LEMBAR MOTTO The dreams cannot come to you.

EM O

The only one who can make the distance between you and your dreams getting closer is yourself.

SY

ST

O

O

LS

D

SO GO CHASE IT!

iv



PUBLIKASI KARYA ILMIAH UNTUK KEPERLUAN AKADEMIS

Nama

: Agustinus Wikrama Darmadipta

Nomor Mahasiswa

: 095314053

EM O

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

Demi mengembangkan ilmu pengetahuan, saya memberikan kepada perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul:

PERBANDINGAN PENGGUNAAN ALGORITMA DIJKSTRA DAN

D

ALGORITMA FLOYD-WARSHALL UNTUK PENCARIAN JALUR TERPENDEK PADA BUS TRANS JOGJA

LS

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

O

kepentingan akademis tanpa perlu meminta izin dari saya maupun memberikan royalti kepada saya selama tetap mencantumkan nama saya sebagai penulis.

O

Demikian pernyataan ini saya buat dengan sebenarnya.

SY

ST

Yogyakarta, 22 Agustus 2013


vi



ABSTRACT

EM O

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

D

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

LS

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

O

in the route of Bus Trans Jogja.

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

O

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

SY

ST

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

viii



tidak menyerah dan selalu bersemangat untuk menyelesaikan tugas akhir ini dengan baik dan tepat waktu.

EM O

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

LS

laboratorium komputer basis data.

D

selalu ceria ketika mengerjakan tugas akhir bersama-sama di

Yogyakarta, 22 Agustus 2013

SY

ST

O

O


x

Penulis



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

EM O

Jarak yang Ditempuh, Melihat Saran Trayek Bus yang Harus Dipilih, dan Melihat Running Time Algoritma ................................................................. 54 3.4.5. 3.5.

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

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

D

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

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

3.7.

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

3.8.

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

3.9.

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

LS

3.6.

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

3.11.

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

O

3.10.

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

O

3.11.2. Desain Antarmuka Jalur Terpendek Telah Ditemukan ................... 79 3.11.3. Desain Antarmuka Tampilan Details .............................................. 80

BAB IV : IMPLEMENTASI ...............................................................................81 Spesifikasi Perangkat Keras dan Lunak ................................................. 81

SY

ST

4.1. 4.2.

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

4.3.

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

4.3.1.

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

xii



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

SY

ST

O

O

LS

D

EM O

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

xiv



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

EM O

Gambar 4.5 Tampilan Halaman Menu ................................................................ 94 Gambar 4.6 Title.xml .......................................................................................... 95 Gambar 4.7 Tampilan Halaman Peta................................................................... 97 Gambar 4.8 activity_main.xml ............................................................................ 98 Gambar 4.9 mydropdownstle.xml ....................................................................... 99 Gambar 4.10 Tampilan Halaman Details .......................................................... 100 Gambar 4.11 Source Code Halaman Details ..................................................... 100 Gambar 4.12 Tampilan Halaman Help .............................................................. 101

D

Gambar 4.13 help.xml ...................................................................................... 108

Gambar 5.1 Source Code Method getMin ......................................................... 116

LS

Gambar 5.2 Source Code Method adjust_sPath ................................................ 117 Gambar 5.3 Source Code Method displayPaths ................................................ 118 Gambar 5.4 Source Code Method findIndex ..................................................... 119 Gambar 5.5 Source Code Method dijkstra ........................................................ 120 Gambar 5.6 Source Code Method findIndex ..................................................... 121

O

Gambar 5.7 Source Code Method deepCopyIntMatrix ..................................... 122

SY

ST

O

Gambar 5.8 Source Code Method Floyd ........................................................... 124

xvi



Tabel 3.10 Tabel Tanggung Jawab Kelas Analisis .................................................... 63 Tabel 3.11 Tabel Operasi dan Atribut Kelas Graph ................................................... 66 Tabel 3.12 Tabel Operasi dan Atribut Kelas Halte .................................................... 67

EM O

Tabel 3.13 Tabel Operasi dan Atribut Kelas TemporaryJalur_n_Jarak ..................... 68 Tabel 3.14 Tabel Operasi dan Atribut Kelas MainActivity ....................................... 68 Tabel 3.15 Tabel Operasi dan Atribut Kelas Map...................................................... 70 Tabel 3.16 Tabel Operasi dan Atribut Kelas PathOverlay ......................................... 70 Tabel 3.17 Tabel Operasi dan Atribut Kelas SitesOverlay ........................................ 72 Tabel 3.18 Tabel Operasi dan Atribut Kelas Help ..................................................... 72

D

Tabel 3.19 Skenario Pengujian ................................................................................... 78

Tabel 5.1 Tabel Hasil Pengujian .............................................................................. 114

SY

ST

O

O

LS

Tabel 5.2 Tabel Hasil Pengujian Running Time Kedua Algoritma .......................... 126

xviii


PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 2

penelitian

ini

adalah

algoritma

yang

masing-masing

menggunakan

strategi/cara berpikir greedy dan dynamic programming (pemrograman

EM O

dinamis). Algoritma Dijkstra merupakan salah satu algoritma yang digunakan dalam penelitian ini di mana cara kerja algoritma tersebut adalah

menggunakan strategi greedy. Algoritma jalur terpendek yang juga digunakan

dalam penelitian ini yang menggunakan strategi pemrograman dinamis adalah algoritma Floyd – Warshall. Alasan digunakannya kedua algoritma tersebut

adalah kedua algoritma tersebut telah sering digunakan untuk kasus pencarian

D

jalur terpendek. Sebagai contoh algoritma Dijkstra pernah dilakukan dalam penilitian kasus pencarian jalur terpendek yang ditempuh oleh sebuah taksi

LS

(Noviani, Enik., dkk., 2012) dan pencarian jalur terpendek yang ditempuh oleh dua transportasi umum di Jakarta, yakni Bus Trans Jakata dan KRL commuter line (Arifianto, Sofyan., 2012). Algoritma Floyd – Warshall juga telah sering digunakan dalam beberapa penlitian mengenai pencarian jalur

O

terpendek, seperti pada penilitian pencarian rute terpendek di kota Surabaya (Purwananto, Yudhi., dkk., 2005) dan pencarian rute terpendek antar gedung

O

di suatu kampus (Fanani, Lutfi., 2012). Kasus pencarian jalur terpendek yang digunakan dalam penelitian ini

SY

ST

adalah kasus pencarian jalur terpendek pada Bus Trans Jogja. Kasus Bus Trans Jogja sesuai digunakan untuk pencarian jalur terpendek karena Bus Trans Jogja memiliki total enam trayek di mana masing-masing trayek memiliki jalur-jalur perjalanan yang berbeda untuk menuju suatu tempat



para pengguna tidak mengalami kebingungan dalam menentukan Bus Trans

1.2.

EM O

Jogja yang harus dipakai guna mencapai suatu tujuan tertentu.

Rumusan Masalah

Seberapa optimal dan efisienkah penggunaan strategi berpikir greedy (algoritma Dijkstra) dan pemrograman dinamis (algoritma Floyd – Warshall) dalam kasus penentuan jalur terpendek yang ditempuh oleh Bus Trans Jogja?

Rumusan masalah di atas diselesaikan dengan mencari nilai dari Big

D

Oh dan waktu yang ditempuh oleh setiap algoritma dalam menyelesaikan kasus pencarian jalur terpendek pada Bus Trans Jogja. Nilai Big Oh dan waktu

LS

yang diperoleh kemudian akan dibandingkan satu sama lain untuk menentukan algoritma mana yang paling optimal untuk kasus tersebut.

1.3.

Tujuan Penelitian

O

Tujuan yang ingin dicapai dari penelitian ini adalah: 1. Untuk mendapatkan kompleksitas waktu asimtotik dan nilai kecepatan

O

waktu dari algoritma greedy dan pemrograman dinamis pada kasus

SY

ST

pencarian jalur terpendek pada Bus Trans Jogja.

1.4.

Batasan Masalah Batasan masalah dari penelitian ini adalah:



Trans Jogja. Kesesuaian tersebut diukur berdasarkan perbandingan dari Big Oh dan waktu penyelesaian yang dihasilkan oleh masing-masing algoritma.

EM O

Manfaat yang lain yang diperoleh dari penelitian ini adalah sebuah aplikasi berbasis android yang dapat digunakan oleh para pengguna Bus Trans

Jogja dalam menentukan bus yang harus dipakai dalam menuju ke suatu tujuan tertentu. Aplikasi tersebut akan mampu memberikan keluaran berupa saran kepada pengguna mengenai bus dengan trayek mana yang harus dipakai

guna menuju suatu tempat dengan cepat. Aplikasi tersebut diharapkan

D

memberi pertolongan kepada masyarakat pengguna Bus Trans Jogja, terutama

para wisatawan pengguna Bus Trans Jogja yang belum paham betul mengenai

SY

ST

O

O

tertentu.

LS

jalur-jalur yang ditempuh oleh Bus Trans Jogja dalam mencapai suatu tujuan



satu algoritma yang mampu digunakan untuk menyelesaikan satu masalah. Masalah yang timbul dari hal tersebut kemudian adalah dalam memilih

EM O

algoritma manakah yang paling optimal atau yang terbaik dalam menyelesaikan masalah yang dihadapi tersebut. Menurut Suryadi MT (1996), pemilihan algoritma terbaik dapat dilakukan dengan memperhatikan kriteriakriteria berikut ini: 1. ada output Berdasarkan

pada

definisi

algoritma

bahwa

algoritma

D

digunakan untuk menyelesaikan suatu masalah, maka berarti

suatu algoritma haruslah mempunyai output. Output tersebut

LS

merupakan sebuah solusi dari masalah yang dipecahkan. 2. efektivitas dan efisiensi

Efektivitas suatu algoritma dapat dilihat dari solusi yang dihasilkan. Solusi tersebut dikatakan efektif bila sesuai dengan

O

masalah yang dipecahkan dan mampu memecahkan masalah tersebut. Jadi dapat dikatakan bahwa suatu algoritma dikatakan

O

efektif jika tepat guna.

SY

ST

Efisiensi suatu algoritma diukur berdasarkan waktu proses dan penggunaan memory dalam menyelesaikan suatu masalah. Semakin kecil waktu proses dan memory yang dibutuhkan dalam menyelesaikan suatu masalah, maka semakin efisien pula suatu algoritma tersebut.



tersusun

dengan

baik

sehingga

memudahkan

untuk

dilakukannya pemeriksaan ulang terhadap algoritma tersebut.

EM O

Selain untuk hal tersebut, algoritma yang memiliki struktur yang baik dapat memungkinkan memiliki waktu proses yang relatif singkat.

Berdasarkan kelima hal di atas, maka algoritma yang baik dapat

didefinisikan sebagai suatu algoritma yang memiliki output yang tepat guna (efektif) dalam waktu yang relatif singkat dan penggunaan memory yang

D

relative sedikit (efisien) dengan langkah yang berhingga dan prosesnya berakhir dengan baik dalam keadaan diperoleh suatu solusi ataupun tidak

2.2.

LS

adanya solusi (Suryadi MT, 1996).

Pengertian Analisis Algoritma

Analisis algoritma dilakukan dengan memperhatikan dua hal, yaitu

O

waktu tempuh dan jumlah memory yang digunakan. Waktu tempuh memiliki definisi sebagai waktu yang diperlukan suatu algoritma dalam mencari solusi

O

atas permasalahan yang diberikan. Waktu yang singkat memberi arti bahwa algoritma yang digunakan efisien. Waktu tempuh yang diperlukan oleh suatu

SY

ST

algoritma menurut Suryadi MT (1996) dipengaruhi oleh beberapa hal, yaitu: 1. banyak langkah Banyaknya langkah yang digunakan dalam suatu algoritma akan menentukan cepat lambatnya proses yang dilakukan oleh



tidak sesuai, maka waktu tempuh yang digunakan algoritma tersebut pun akan membesar (lambat).

EM O

Jumlah memory juga perlu diperhatikan dalam menganalisis suatu algoritma agar suatu proses dapat berjalan lancar tanpa ada hambatan. Hal yang mempengaruhi dalam pemakaian memory adalah jenis variable dan data yang digunakan pada suatu algoritma. Oleh karena itu pengalokasian memory

perlu diperhitungan berdasarkan dua hal tersebut agar lambatnya waktu tempuh yang terjadi karena kekurangan memory dapat dihindari.

D

Kompleksitas waktu asimtotik algoritma juga merupakan hal yang peru diperhatikan dalam melakukan analisis terhadap suatu algoritma.

LS

Kompleksitas waktu asimtotik algoritma dinyatakan dalam suatu fungsi F(N) untuk kebutuhan waktu tempuh dan penyimpanan untuk sejumlah N masukan data. Fungsi F(N) tersebutlah yang kemudian dinyatakan sebagai Big Oh. Jika F(N) adalah fungsi Polinomial dalam N dengan derajat (tingkat) m, yang

O

ditulis dengan notasi:

F(N) = a m Nm + a m-1 Nm-1 + . . . + a 1 N + a 0

O

maka Big Oh dari F(N) adalah Nm yang dinotasikan: F(N) = O(Nm) (Suryadi MT, 1996). Berikut ini adalah pengelompokan algoritma berdasarkan notasi

SY

ST

Big Oh :

Kelompok Algoritma O(1)

Nama Konstan



berikut ini. Graf ini menggambarkan hubungan dari suatu tempat ke tempat yang lain. Node menggambarkan suatu tempat dan vertex menggambarkan

EM O

bobot atau jarak yang menghubungkan antar tempat.

D

Gambar 2.1 Contoh Graph (Dijkstra)

Langkah pertama yang dilakukan pada strategi ini adalah menentukan

LS

titik awal dan titik tujuan (dalam kasus ini node satu adalah titik awal dan node sepuluh adalah titik tujuan). Berangkat dari node satu, terdapat tiga jalur yang dapat ditempuh yakni jalur dengan nilai jarak 300, 200, dan 350. Jalur yang dipilih adalah jalur dengan nilai jarak 200 karena merupakan nilai yang

O

paling optimal (rendah) di antara ketiga nilai tersebut. Pemilihan jalur tersebut menunjukkan bahwa node kedua yang dilalui adalah node tiga. Pada node

O

tiga, nilai jarak yang kemudian dipilih adalah nilai 280 yang kemudian membawa menuju node enam dari nilai 350, 280, dan 410. Node delapan

SY

ST

kemudian menjadi tujuan berikutnya setelah melakukan pemilihan nilai jarak yang paling optimal antara nilai 350 dan 380. Langkah berikutnya adalah memilih satu-satunya nilai yang membawa ke tujuan akhir (node sepuluh), yakni memilih jalur dengan nilai 380. Pencarian jalur terpendek menggunakan



7.

d (7) = ?

8.

d (8) = ?

9.

d (9) = ?

EM O

16

10. d (10) = ? 1-3

Iterasi II (posisi awal di titik 3)

d(2) = min {d(2), d(3) + a(3,2)} = min (300, 200 + ?) = 300

2.

d(4) = min {d(4), d(3) + a(3,4)} = min (350, 200 + ?) = 350

3.

d(5) = min {d(5), d(3) + a(3,5)} = min (?, 200 + 350) = 550

4.

d(6) = min {d(6), d(3) + a(3,6)} = min (?, 200 + 280) = 480

5.

d(7) = min {d(7), d(3) + a(3,7)} = min (?, 200 + 410) = 610

6.

d(8) = min {d(8), d(3) + a(3,8)} = min (?, 200 + ?) = ?

7.

d(9) = min {d(9), d(3) + a(3,9)} = min (?, 200 + ?) = ?

8.

d(10) = min {d(10), d(3) + a(3,10)} = min (?, 200 + ?) = ?

O

LS

D

1.

O

1–2

SY

ST

Iterasi III (posisi awal di titik 2) 1. d(4) = min {d(2), d(2) + a(2,4)} = min (350, 300 + ?) = 350 2. d(5) = min {d(5), d(2) + a(2,5)} = min (550, 300 + 320) = 550 3. d(6) = min {d(6), d(2) + a(2,6)} = min (480, 300 + 350) = 480 4. d(7) = min {d(7), d(2) + a(2,7)} = min (610, 300 + 400) = 610



Iterasi VI (posisi awal di titik 5) 1. d(7) = min {d(7), d(5) + a(5,7)} = min (550, 550 + ?) = 550

EM O

2. d(8) = min {d(8), d(5) + a(5,8)} = min (830, 550 + 210) = 760 3. d(9) = min {d(9), d(5) + a(5,9)} = min (860, 550 + 230) = 780 4. d(10) = min {d(10), d(5) + a(5,10)} = min (?, 550 + ?) = ? 1–4–7

Iterasi VII (posisi awal di titik 7)

D

1. d(8) = min {d(8), d(7) + a(7,8)} = min (760, 550 + 210) = 760

2. d(9) = min {d(9), d(7) + a(7,9)} = min (780, 550 + 290) = 780

LS

3. d(10) = min {d(10), d(7) + a(7,10)} = min (?, 550 + ?) = ? 1–3–5–8

Iterasi VIII (posisi awal di titik 8)

O

1. d(9) = min {d(9), d(8) + a(8,9)} = min (780, 760 + ?) = 780 2. d(10) = min {d(10), d(8) + a(8,10)} = min (?, 760 + 380) = 1140

SY

ST

O

1–3–5–9

Iterasi IX (posisi awal di titik 9) 1.

d(10) = min {d(10), d(9) + a(9,10)} = min (1140, 780 + 280) = 1060

1 – 3 – 5 – 9 – 10



nilai yang terdapat pada vertex-vertex tersebut menggambarkan nilai jarak

EM O

antara satu node ke node yang lain.

D

Gambar 2.2 Contoh Graph (Pemrograman Dinamis)

Langkah pertama yang dilakukan adalah ambil salah satu node sebagai tujuan, dalam hal ini node dengan label sepuluh adalah tujuan yang ingin

LS

dicapai. Berangkat dari hal tersebut dapat dilihat bahwa untuk mencapai node sepuluh tersebut perlu melalui node delapan atau sembilan. Berdasarkan hal tersebut maka dihasilkanlah sebuah table berikut ini yang menggambarkan

O

langkah pertama.

SY

ST

O

Langkah I

Nilai

Jalur yang

Jarak

Ditempuh

8

380

8-10

9

280

9-10

Node

Tabel 2.2 Langkah I Strategi Pemrograman Dinamis

Langkah yang dilakukan berikutnya adalah menentukan jalur

terpendek untuk menuju node delapan dan sembilan yang kemudian menuju ke node tujuan. Jika berangkat melalui node lima maka nilai jarak yang



870 (200+670). Oleh karena itu, nilai jarak yang dipilih kemudian adalah 810. Tabel yang menggambarkan hasil dari langkah ini adalah tabel 2.4:

Langkah III

Jalur yang

EM O

Nilai

Node

Jarak

Ditempuh

2

830

2-5-9-10

3

860

4

810

3-5-9-10 4-5-9-10

Tabel 2.4 Langkah III Strategi Pemrograman Dinamis

Langkah keempat yang juga merupakan langkah terakhir untuk kasus

D

ini adalah menentukan nilai jalur terpendek jika melalui node satu. Nilai-nilai

jarak yang dihasilkan adalah 1130 (300+830), 1060 (200+860), dan 1160 (350+810). Berdasarkan nilai-nilai yang dihasilkan tersebut maka 1060 adalah

Langkah IV

LS

nilai yang dipilih. Tabel yang dihasilkan dari langkah ini adalah tabel 2.5: Node

1

Nilai

Jalur yang

Jarak

Ditempuh

1060

1-3-5-9-10

O

Tabel 2.5 Langkah IV Strategi Pemrograman Dinamis

Nilai tersebut merupakan nilai akhir yang didapat dari kasus ini. Nilai

O

1060 juga merupakan nilai jarak terpendek yang dihasilkan untuk mencapai node sepuluh dari node satu. Hal tersebut menunjukkan bahwa jalur 1-3-5-9-

SY

ST

10 merupakan jalur yang harus ditempuh agar hasil yang dicapai adalah optimal (jalur terpendek). Salah satu algoritma pencarian jalur terpendek yang menggunakan

strategi pemrograman dinamis dalam cara penyelesaiannya adalah algoritma



9

?

?

?

?

?

?

?

?

0

280

10

?

?

?

?

?

?

?

?

?

0

Iterasi II 2

3

4

5

6

7

8

9

10

1

0

300

200

350

620

650

700

?

?

?

2

?

0

?

?

320

350

400

?

?

?

3

?

?

0

?

350

280

410

?

?

?

4

?

?

?

0

300

250

200

?

?

?

5

?

?

?

?

0

?

?

210

230

?

6

?

?

?

?

?

0

?

350

380

?

7

?

?

?

?

?

?

0

290

400

?

8

?

?

?

?

?

?

?

0

?

380

9

?

?

?

?

?

?

?

?

0

280

10

?

?

?

?

?

?

?

?

?

0

LS

D

1

EM O

Tabel 2.7 Iterasi I Algoritma Floyd – Warshall

O

Tabel 2.8 Iterasi II Algoritma Floyd – Warshall

Iterasi III 2

O

1

4

5

6

7

8

9

10

1

0

300

200

350

550

480

610

?

?

?

2

?

0

?

?

320

350

400

?

?

?

3

?

?

0

?

350

280

410

?

?

?

4

?

?

?

0

300

250

200

?

?

?

5

?

?

?

?

0

?

?

210

230

?

6

?

?

?

?

?

0

?

350

380

?

ST

SY

3



?

?

?

?

0

?

?

210

230

?

6

?

?

?

?

?

0

?

350

380

?

7

?

?

?

?

?

?

0

290

400

?

8

?

?

?

?

?

?

?

0

?

380

9

?

?

?

?

?

?

?

?

0

280

10

?

?

?

?

?

?

?

?

?

0

8

9

10

EM O

5

Tabel 2.11 Iterasi V Algoritma Floyd – Warshall

Iterasi VI 2

3

4

5

6

7

1

0

300

200

350

550

480

550

760

780

?

2

?

0

?

?

320

350

400

530

550

?

3

?

?

0

?

350

280

410

560

580

?

4

?

?

?

0

300

250

200

510

530

?

5

?

?

?

?

0

?

?

210

230

?

6

?

?

?

?

?

0

?

350

380

?

7

?

?

?

?

?

?

0

290

400

?

8

?

?

?

?

?

?

?

0

?

380

9

?

?

?

?

?

?

?

?

0

280

10

?

?

?

?

?

?

?

?

?

0

O

LS

D

1

O

Tabel 2.12 Iterasi VI Algoritma Floyd – Warshall

SY

ST

Iterasi VII

1

2

3

4

5

6

7

8

9

10

1

0

300

200

350

550

480

550

760

780

?

2

?

0

?

?

320

350

400

530

550

?



0

300

200

350

550

480

550

760

780

1060

2

?

0

?

?

320

350

400

530

550

830

3

?

?

0

?

350

280

410

560

580

860

4

?

?

?

0

300

250

200

490

530

810

5

?

?

?

?

0

?

?

210

230

510

6

?

?

?

?

?

0

?

350

380

660

7

?

?

?

?

?

?

0

290

400

670

8

?

?

?

?

?

?

?

0

?

380

9

?

?

?

?

?

?

?

?

0

280

10

?

?

?

?

?

?

?

?

?

0

EM O

1

D

Tabel 2.15 Iterasi IX Algoritma Floyd – Warshall

Iterasi X 3

4

5

6

7

8

9

10

1

0

300

200

350

550

480

550

830

860

1060

2

?

0

?

?

320

350

400

530

550

830

3

?

?

0

?

350

280

410

560

580

860

4

?

?

?

0

300

250

200

490

530

810

5

?

?

?

?

0

?

?

210

230

510

6

?

?

?

?

?

0

?

350

380

660

7

?

?

?

?

?

?

0

290

400

670

8

?

?

?

?

?

?

?

0

?

380

9

?

?

?

?

?

?

?

?

0

280

?

?

?

?

?

?

?

?

?

0

O ST

SY

10

LS

2

O

1

Tabel 2.16 Iterasi X algoritma Floyd – Warshall Hasil jalur terpendek yang dihasilkan oleh algoritma ini untuk jalur

terpendek yang ditempuh dari node satu ke node sepuluh adalah 1060.



1. Jalur 1A Tempat-tempat yang dilalui oleh jalur ini adalah Candi

EM O

Prambanan - Bandar Udara Adisutjipto - Jembatan Layang Janti - Ambarrukmo Plaza - UIN Sunan Kalijaga - Saphir Square - Bioskop XXI, Jl. Solo - Rumah Sakit Bethesda, Toko Buku Gramedia, Hotel Novotel - Hotel Santika, Pizza Hut

Tugu Jogja - Kantor Kedaulatan Rakyat - Stasiun Tugu – Jogjakarta - Jalan Malioboro (ada 3 buah halte) - Kantor Pos

D

Besar, Kraton, Alun-Alun Utara, Monumen 1 Maret, Benteng

Vredeburg - Taman Pintar, Taman Parkir Bank - Indonesia,

LS

Pasar Beringhardjo, Gondomanan - Pasar Sentul (Jl. Taman Siswa) - Taman Makan Pahlawan Kusumanegara - Balaikota Jogjakarta - Kebun Binatang - Gembira Loka - Jogja Expo Center - Jembatan Janti (kembali ke arah Kalasan, Bandar

O

Udara Adisutjipto sampai Terminal Prambanan)

2. Jalur 1B

O

Tempat-tempat yang dilalui oleh jalur ini adalah Terminal

SY

ST

Prambanan – Kalasan - Bandara Adisucipto – Maguwoharjo Janti (lewat bawah) - Blok O – JEC - Babadan Gedongkuning Gembira Loka – SGM - Pasar Sentul – Gondomanan - Kantor Pos Besar - RS.PKU Muhammadiyah - Pasar Kembang – Badran - Bundaran SAMSAT – Pingit – Tugu – Gramedia -



5. Jalur 3A Tempat-tempat yang dilalui oleh jalur ini adalah Terminal

EM O

Giwangan – Tegalgendu - HS-Silver - Jl. Nyi Pembayun Pegadaian Kotagede – Basen – Rejowinangun - Babadan Gedongkuning – JEC - Blok O - Janti (lewat atas) – Janti –

Maguwoharjo - Bandara ADISUCIPTO – Maguwoharjo -

Ringroad Utara - Terminal Condongcatur – Kentungan - MM UGM – MirotaKampus – Gondolayu – Tugu – Pingit -

D

Bundaran SAMSAT – Badran – PasarKembang - Stasiun TUGU – Malioboro - Kantor Pos Besar - RS PKU

LS

Muhammadiyah – Ngabean - Jokteng Kulon - Plengkung Gading - Jokteng Wetan – Tungkak – Wirosaban – Tegalgendu - Terminal Giwangan. 6. Jalur 3B

O

Tempat-tempat yang dilalui oleh jalur ini adalah Terminal Giwangan – Tegalgendu – Wirosaban – Tungkak - Jokteng

O

Wetan - Plengkung Gading - Jokteng Kulon – Ngabean - RS

SY

ST

PKU Muhammadiyah - Pasar Kembang – Badran - Bundaran SAMSAT – Pingit – Tugu – Gondolayu - Mirota Kampus MM UGM – Kentungan - Terminal Condong Catur - Ringroad Utara – Maguwoharjo - Bandara Adisucipto – Maguwoharjo JANTI (lewat bawah) - Blok O – JEC - Babadan



BAB III

EM O

ANALISA DAN PERANCANGAN SISTEM Pada bab ini akan dijelaskan mengenai analisa dan perancangan sistem yang digunakan dalam penelitian ini. 3.1.

Deskripsi Kasus

Kasus penggunaan Bus Trans Jogja yang mungkin dihadapi oleh para penumpangnya adalah ketidaktahuan untuk menentukan jalur Bus Trans Jogja

D

yang harus ditempuh guna mencapai tujuan yang dikehendaki. Selain hal itu, penumpang bahkan juga mungkin tidak tahu trayek apa yang harus ditumpangi dan perpindahan bus yang harus dilakukan guna mencapai titik

LS

tujuannya dengan cepat. Berdasarkan hal tersebut salah satu solusi yang dapat diberikan adalah membuat sebuah aplikasi untuk mencari jalur terpendek rute Bus Trans Jogja dari satu titik awal ke satu titik tujuan. Selain kemampuan

O

mencari jalur terpendek, aplikasi yang dibuat juga harus mampu memberikan saran berupa bus yang harus digunakan beserta perpindahan yang harus

O

dilakukan untuk menempuh jalur terpendek yang telah ditemukan. Aplikasi akan dibuat untuk smartphone bersistem operasi Android.

SY

ST

Hal tersebut dilakukan agar aplikasi yang dibuat lebih optimal dalam membantu penumpang karena mampu membantu penumpang pemilik smartphone Android menentukan Bus Trans Jogja yang harus digunakan

secara mobile. Pertimbangan hal tersebut muncul karena dengan ukuran

34



gambar graph yang terbentuk berdasarkan posisi halte dan jarak antar halte

SY

ST

O

O

LS

D

EM O

yang ada.

Gambar 3.1 Graph Rute Bus Trans Jogja



SY

ST

O

O

LS

D

EM O

38

Gambar 3.2 Posisi Halte Bus Trans Jogja



12. Untuk int i = 1, selama i < jumlah vertex lakukan langkah dua belas hingga langkah lima belas.

EM O

13. Jika vertex ke – i belum dikunjungi dan sPath ke – i < jarakTerpendek maka lakukan langkah tiga belas dan empat belas. 14. jarakTerpendek = sPath[i].getjarak(). 15. minIndeks = i. 16. i++.

18. Buat

dan

D

17. Buat dan inisialisasi variabel “min” = minIndeks. inisialisasi

“minDist”

=

LS

sPath[min].getJarak().

varaibel

19. Jika minDist = infinite, maka break. Jika tidak lakukan langkah dua puluh dan 21.

20. vertSekarang = minIndeks.

O

21. jarakAwalKini = sPath[min].getJarak().

22. Tandai vertex sekarang bahwa dirinya sudah dikunjungi.

O

23. jumGraph++.

SY

ST

24. Buat dan inisialisasi variabel int “kolom” = 0. 25. Selama kolom < jumlah vertex, lakukan langkah 26 hingga 31. 26. Jika vertex dengan index kolom sudah dikunjungi, maka kolom++ dan continue.



5. Untuk int i = 0, selama i < path.length lakukan langkah enam hingga langkah sembilan.

EM O

6. Untuk int j = 0, selama j < path.length lakukan langkah tujuh hingga langkah delapan.

7. Jika “jarak” sama dengan infinite, maka path[i][j] = -1, jika tidak maka path[i][j] = i. 8. j++. 9. i++.

D

10. Untuk int i = 0, selama i < jumlah halte, lakukan langkah sebelas hingga langkah dua belas.

12. i++.

LS

11. path[i][i] = 1.

13. Untuk int i = 0, selama i < path.length lakukan langkah empat belas hingga langkah 21.

O

14. Untuk int j = 0, selama j < path.length lakukan langkah lima belas hingga langkah dua puluh.

O

15. Untuk int k = 0, selama k < path.length lakukan langkah enam

SY

ST

belas hingga langkah sembilan belas.

16. Jika jarak[j][i] + jarak[i][k] < jarak[j][k], lakukan langkah tujuh belas dan delapan belas. 17. jarak[j][k] = jarak[j][i] + jarak[i][k]. 18. path[j][k] = path[i][k].



9. Masukkan ke daftarTrayek edgeTrayek untuk nilai awal dan tujuan yang telah ditentukan pada langkah tujuh dan delapan.

EM O

10. i++. 11. Inisialisasi bantu yang bertipe List<String> yang merupakan nilai dari variabel daftarTrayek ke-0.

12. Inisialisasi variabel bertipe String baru dan perpindahanBus bernilai empty string.

13. Untuk int i = 1, selama i kurang dari jalurPilihan.size maka

D

lakukan langkah empat belas hingga langkah 29. 14. Ubah nilai variabel baru menjadi empty string.

LS

15. Untuk int j = 0, selama j kurang dari bantu.size, lakukan langkah enam belas hingga sembilan belas. 16. Untuk int k = 0, selama k kurang dari daftarTrayek.get(i).size lakukan langkah tujuh belas hingga delapan belas.

O

17. Jika nilai variabel bantu sama dengan daftarTrayek.get(i).get(k) maka baru = baru + bantu.get(j).

O

18. j++.

SY

ST

19. j++. 20. Jika nilai variabel baru sama dengan empty String maka lakukan langkah 21 hingga 25, jika tidak lakukan langkah 26. 21. Untuk j = 0, selama j kurang dari bantu.size lakukan langkah 22 hingga 24.



dengan solusi yang diperoleh melalui penghitungan manual. Kemiripan solusi yang diberikan oleh sistem dengan solusi yang didapat secara manual akan

EM O

menjadi nilai ukur kebenaran dari solusi yang diberikan oleh sistem. Semakin mirip solusi dari sistem dengan solusi yang didapat dari perhitungan manual,

maka semakin benar pula solusi yang diberikan oleh sistem. Penghitungan manual akan dilakukan dengan cara:

1. Menentukan semua kemungkinan jalur yang mampu ditempuh dari

titik awal dan tujuan yang telah ditentukan, kemudian menghitung

D

jarak untuk setiap kemungkinan jalur yang didapat.

2. Membandingkan semua jarak untuk semua kemungkinan jalur yang

LS

telah didapat.

3. Jalur dengan nilai jarak terkecillah yang kemudian dijadikan sebagai solusi dalam penghitungan manual tersebut. Hal terakhir yang kemudian dilakukan adalah membandingkan

O

kompleksitas waktu asimtotik dari masing-masing algoritma dan running time-nya. Hal ini dilakukan untuk menentukan algoritma mana yang paling

O

optimal untuk digunakan dalam aplikasi yang dibuat. Algoritma yang palling optimallah yang akan benar-benar digunakan dalam aplikasi yang akan dibuat

SY

ST

sehingga aplikasi benar-benar siap untuk dipublikasi dan digunakan oleh masyarakat umum.



EM O

3. Aktor menyentuh kembali titik awal yang telah ditentukan sebelumnya.

2. Sistem telah menandai lokasi awal yang telah ditentukan oleh aktor.

4. Sistem memunculkan dialog apakah titik awal yang telah ditentukan sebelumnya oleh actor akan dibatalkan atau tidak. Tabel 3.1 Tabel Use Case Menentukan Titik Awal

: Menentukan titik tujuan

Aktor

: User (pengguna aplikasi)

Kondisi Awal

: Titik awal telah ditentukan

Skenario

:

D

Nama Use Case

LS

b.

Aksi Aktor

Reaksi Sistem

1. Aktor touch titik tujuan yang berupa icon halte Bus Trans Jogja.

O

O

2. Sistem menandai lokasi yang telah ditentukan dan kemudian menampilkan jalur yang menghubungkan tiap halte. Tabel 3.2 Tabel Use Case Menentukan Titik Tujuan

SY

ST

c.

Nama Use Case

: Melihat jalur bus yang ditempuh

Aktor

: User (pengguna aplikasi)

Kondisi Awal

: Titik awal dan tujuan telah ditentukan

Skenario

:



Dipilih

Nama Use Case

: Melihat running time algoritma

Aktor

: User

Kondisi Awal

: Titik awal dan tujuan telah ditentukan

Skenario

: Aksi Aktor

1. Aktor touch tombol “Details”.

D

f.

EM O

bus yang harus dipilih aktor berdasarkan jalur terpendek yang telah diperoleh sistem. Tabel 3.5 Tabel Use Case Melihat Saran Trayek Bus yang Harus

Reaksi Sistem

Nama Use Case

: Mencari halte

Aktor

: User

O

g.

LS

2. Sistem menampilkan running time aloritma. Tabel 3.6 Tabel Use Case Melihat Running Time Algoritma

:-

Skenario

:

SY

ST

O

Kondisi Awal

Aksi Aktor

1. Aktor mengisi textfield yang ada dengan nama halte yang ingin dicari. 2. Aktor touch tombol “Cari”.

Reaksi Sistem

3. Sistem menunjukkan halte yang dicari jika ada.



Diagram Aktivitas Menentukan Titik Awal

EM O

3.4.1.

Gambar 3.4 Diagram Aktivitas Menentukan Titik Awal

D

Diagram Aktivitas Menentukan Titik Tujuan

LS

3.4.2.

SY

ST

O

O

Gambar 3.5 Diagram Aktivitas Menentukan Titik Tujuan



3.4.4.

Diagram Aktivitas Melihat Jalur Bus yang Ditempuh,

EM O

Melihat Nilai Jarak yang Ditempuh, Melihat Saran Trayek Bus yang Harus Dipilih, dan Melihat Running Time

SY

ST

O

O

LS

D

Algoritma

Gambar 3.7 Diagram Akivitas Melihat Jalur Bus yang

Ditempuh, Melihat Nilai Jarak yang Ditempuh, Melihat Saran Trayek Bus yang Harus Dipilih, dan Melihat Running Time Algoritma



Diagram Sekuensial Menentukan Titik Tujuan

D

EM O

3.5.2.

Diagram Sekuensial Mencari Halte

SY

ST

O

O

3.5.3.

LS

Gambar 3.10 Diagram Sekuensial Menentukan Titik Tujuan

Gambar 3.11 Diagram Sekuensial Mencari Halte



D

EM O

58

LS

Gambar 3.13 Diagram Sekuensial Melihat Jalur Bus yang Ditempuh, Melihat Nilai Jarak yang Ditempuh, Melihat Saran Trayek Bus yang Harus Dipilih, dan Melihat Running Time Algoritma Floyd-

O

Warshall

Diagram Sekuensial Melihat Help

SY

ST

O

3.5.5.



O

LS

D

EM O

60

3.7.

O

Gambar 3.16 Diagram Kelas Perancangan Keseluruhan

Kelas Analisis

SY

ST

Tabel 3.9 dan 3.10 adalah tabel kelas-kelas analisis yang digunakan

pada sistem. Tabel ini menunjukkan jenis-jenis setiap kelas yang digunakan

dan tanggung jawab dari setiap kelas. Daftar attribut setiap kelas juga dimasukkan dalam tabel ini.



EM O

double jarak private int from

MapView mapView MapController mapController SitesOverlay sitesOverlays SitesOverlay sitesOverlay2 Graph graph Button buttonDetails List<String> daftarHalte InputStream data Sheet sheet Sheet sheet2 Sheet sheet3 ArrayList<String> trayek String param String[] namaHalte GeoPoint pointHalte1 AutoCompleteTextView autoText Projection projection ArrayList ppoint List items Drawable marker Drawable markerStart Drawable markerEnd Drawable markerChange Context context

O

LS

D

TemporaryJalur_n_Jarak Membantu untuk menyimpan jarak dan jalur secara sementara yang digunakan dalam pencarian jalur terpendek dengan menggunakan algoritma dijkstra. MainActivity Menampilkan halaman judul. Map Menampilkan tampilan peta. Membuat halte dan jarak antar halte. Membuat posisiposisi halte dan pengguna pada peta.

O

PathOverlay

SY

ST

SitesOverlay

Membuat terpendek peta. Menampilkan posisi-posisi dan pengguna peta. Menampilkan terpendek

jalur pada

halte pada jalur pada



findIndex(String index)

public

Digunakan mencari node

untuk

index yang

dicari

masukan

EM O

dengan

dari

berupa nama node.

getMin()

public

Digunakan mencari

untuk

jalur

terpendek

yang

dengan

membandingkan

dua

buah jalur. Fungsi ini

D

digunakan

dalam

pencarian

jalur

terpendek

dengan

algoritma Dijkstra.

adjust_sPath()

O

LS

public

displayPaths(int

tujuan,

int public

O ST

untuk

membentuk

jalur

terpendek

pada

pencarian

jalur

terpendek

dengan

algoritma Dijkstra.

awal)

SY

Digunakan

Digunakan

untuk

menampilkan

jarak

terpendek dan jalur yang harus ditempuh dalam pencarian jalur terpendek

dengan

algoritma Dijkstra. dijkstra(String

awal,

String public

Digunakan

untuk



diperoleh. Visibility

Tipe

INFINITE

private

integer

edge

package

double[][]

edgeTrayek

package

daftarVertex

package

jumlah_vertex

package

tujuan

package

sPath

package

EM O

Nama Atribut

ArrayList<String>[][] Halte[]

integer

List

TemporaryJalur_n_Jar

jumGraph

package

vertSkrg

D

ak[]

mulaiSmpSkrg

integer

package

integer

package

double

LS

Tabel 3.11 Tabel Operasi dan Atribut Kelas Graph

Visibility

Keterangan

getNama()

public

Digunakan

O

b. Kelas Halte Nama Operasi

O

setNama(String nama)

SY

ST

isInGraph()

untuk

mengambil nama dari halte.

public

Digunakan

untuk

memberi nama sebuah halte. public

Digunakan

untuk

mengambil tanda sebuah halte

apakah

sudah

dikunjungi atau belum. setInGraph(boolean

public

Digunakan

untuk



asal

node

sementara. Visibility

Tipe

jarak

private

double

from

private

EM O

Nama Atribut

integer

Tabel 3.13 Tabel Operasi dan Atribut Kelas TemporaryJalur_n_Jarak

d. Kelas MainActivity Nama Operasi

Visibility

Keterangan

onCreate(Bundle

public

Digunakan

untuk

memanggil

dan

savedInstanceState)

D

menampilkan

halaman

judul.

-

Visibility

LS

Nama Atribut

Tipe

Tabel 3.14 Tabel Operasi dan Atribut Kelas MainActivity

Visibility

protected Digunakan

untuk

memanggil

dan

onCreateOptionsMenu(Menu

public

onCreate(Bundle

O

savedInstanceState)

menampilkan peta.

ST

menu)

SY

Keterangan

O

e. Kelas Map Nama Operasi

onBackPressed()

Digunakan membuat

untuk menu

pada

aplikasi. public

Digunakan

untuk

memberi action apa yang harus dilakukan ketika



autoText

package

AutoCompleteTextView

Tabel 3.15 Tabel Operasi dan Atribut Kelas Map

EM O

f. Kelas PathOverlay Nama Operasi Visibility

Keterangan

draw(Canvas canvas, public

Digunakan

MapView mapView, boolean

untuk

membuat gambar path

shadow,

yang akan ditampilkan

long when)

di peta.

Visibility

projection

private

ppoint

private

Tipe

Projection

ArrayList

D

Nama Atribut

Tabel 3.16 Tabel Operasi dan Atribut Kelas PathOverlay

Visibility

Keterangan

createItem(int index)

protected

Digunakan

untuk

membuat

objek

O

LS

g. Kelas SitesOverlay Nama Operasi

SY

ST

O

size()

addItem(OverlayItem

public

gambar

(posisi

dan

halte). Digunakan

untuk

mengambil jumlahnya objek

gambar

yang

dibuat. public

item)

Digunakan

untuk

menambahkan

objek

gambar. addFlag(int[] itemSize)

public

Digunakan

untuk



int counter3 = -1

package

integer

mapView

package

MapView

param

package

String

EM O

Tabel 3.17 Tabel Operasi dan Atribut Kelas SitesOverlay

h. Kelas Help Nama Operasi

Visibility

Keterangan

onCreate(Bundle

public

Digunakan

untuk

memanggil

dan

savedInstanceState)

menampilkan

halaman

Help.

-

Visibility

Tipe

D

Nama Atribut

3.9.

Cara Pengujian

LS

Tabel 3.18 Tabel Operasi dan Atribut Kelas Help

Pengujian dilakukan dengan dua macam. Pengujian pertama dilakukan

O

untuk menguji dari kebenaran sistem atau aplikasi yang telah dibuat. Pengujian ini dilakukan dengan memberikan sejumlah kasus terhadap aplikasi

O

yang telah dibuat. Hasil yang diperoleh berdasarkan setiap kasus yang diberikan kemudian akan dibandingkan dengan perhitungan manual untuk

SY

ST

kasus yang sama. Perbandingan tersebut dilakukan untuk menguji akurasi kebenaran atas solusi jalur terpendek yang diberikan aplikasi. Setelah perbandingan untuk mengetahui tingkat kebenaran dilakukan maka hal berikutnya yang dilakukan adalah menghitung nilai kompleksitas waktu



titik awal.

pada peta.

disentuh

akan

2

sebagai

awal. Membatalkan

Halte bus yang telah Muncul

titik awal.

ditentukan

titik

pesan

sebagai apakah

titk

titik

awal

awal akan dibatalkan atau

sebelumnya. 3

baru

EM O

ditandai dengan ikon

tidak.

Menentukan

Halte bus yang ada Halte

titik tujuan.

pada

peta

bus

(selain disentuh

yang

akan

sebagai titik awal).

D

yang telah ditandai ditandai dengan ikon baru

sebagai

titik

tujuan.

Muncul garis pada

LS

peta

yang

menghubungkan

Melihat

jalur Tombol

bus

yang disentuh.

O

4

O

antar

SY

ST

ditempuh.

5

yang

merupakan

jalur

tempuh

titik

dari

awal ke titik tujuan. “Details” Rute jalur terpendek yang harus ditempuh menggunakan

bus

akan muncul berupa poin-poin.

Melihat

nilai Tombol

jarak

yang disentuh.

ditempuh.

halte

“Details” Tampil total nilai jarak terpendek yang harus

ditempuh



(KENTUNGAN)

SUGIYONO

2 User diarahkan ke posisi

halte

PERJUANGAN)

SUGIYONO

EM O

(MUSEUM

2

(MUSEUM

PERJUANGAN) 9

Mencari halte.

“”

Tampil pesan bahwa halte

yang

dicari

TINUS

D

tidak diketahui.


yang

dicari

LS

tidak diketahui.

SEMBARANG


yang

dicari

tidak diketahui.

Menguji

Awal: SUDIRMAN Jarak: 4,604 km

O

10

kebenaran jarak 2 (BUMI PUTERA)

Jalur:

terpendek

-SUDIRMAN

2

(BUMI PUTERA)

algoritma

-MANGKUBUMI 1

O

masing-masing

ST

SY

Tujuan: NGABEAN

(TUGU) -MANGKUBUMI 2 (PLN) -MALIOBORO (GARUDA)

1



Naik 2B.

HARYONO (SMA 7)

MT Jarak: 4,299 km 2 Jalur: -MT HARYONO 2

EM O

Awal:

Tujuan: TENTARA (SMA 7)

PELAJAR 1 (SMP -TEJOKUSUMAN 14)

-NGABEAN -

COKROAMINOTO (SMA 1)

D

-SMPN 11

-TENTARA

PELAJAR 1 (SMP 14)

LS

Saran: Naik 3B – pindah ke 2B di Ngabean.

3.11.

O

Tabel 3.19 Skenario Pengujian

Desain Antarmuka

O

Gambar-gambar berikut adalah rancangan dari antarmuka untuk sistem

SY

ST

yang akan dibuat.



Desain Antarmuka Tampilan Details

D

EM O

3.11.3.

SY

ST

O

O

LS

Gambar 3.19 Desain Antarmuka Tampilan Details



4.2.

Pengolahan Data Data

diperoleh

dari

Dinas

Perhububungan

Komunikasi

dan

EM O

Informatika. Berdasarkan dari data yang diperoleh tersebut terdapat enam trayek Bus Trans Jogja yang beroperasi hingga pada saati ini. Trayek tersebut

adalah trayek 1A, 1B, 2A, 2B, 3A, dan 3B. Halte yang aktif terdapat seratus satu buah.

Data yang dibutuhkan adalah nama halte, posisi halte, dan jarak tiap halte yang ditelusuri oleh masing-masing trayek. Data disimpan pada file

D

excel yang mengandung 3 sheet. Berikut ini adalah penjelasan dari kegunaan masing-masing sheet:

LS

1. Sheet I (Halte) Sheet ini digunakan untuk menyimpan nama asli setiap halte. Nama asli halte inilah yang kemudian akan dibentuk menjadi pada graph yang dibentuk. Sheet

ini terdiri satu

O

node-node

kolom yang berisi nama-nama asli setiap halte.

O

2. Sheet II (Jarak)

Sheet ini digunakan untuk menyimpan jarak tiap halte. Pada sheet

SY

ST

ini terdapat lebih dari empat kolom. Kolom pertama digunakan untuk menyimpan titik awal halte. Kolom kedua digunakan untuk menyimpan titik tujuan halte. Kolom ketiga digunakan untuk menyimpan jarak dari titik awal halte ke titik tujuan halte. Kolom



algoritma Dijkstra dan Floyd-Warshall. Penghitungan perpindahan bus

EM O

dilakukan pada gambar source code 4.3.3. 4.3.1. Implementasi Metode Greedy dengan Algoritma Dijkstra

Source code pada gambar 4.1 adalah source code dari yang

digunakan untuk mengimplementasikan algoritma dijkstra ke dalam aplikasi. Source code menunjukkan bahwa dibutuhkan tiga method

bantuan dalam pengimplementasian algoritma dijkstra ke dalam

D

aplikasi. Tiga method bantuan yang digunakan, yakni method getMin(), adjust_sPath(), dan displayPaths(int tujuan, int awal). Method getMin() digunakan untuk menemukan nilai jarak

LS

terpendek sementara untuk setiap node yang ada dalam graph. Jarak terpendek ini digunakan sebagai pembanding dalam rangka menemukan jarak terpendek setiap node yang sebenarnya. Method

O

adjust_sPath() digunakan untuk memberntuk jalur berdasarkan jarak terpendeknya. Terakhir adalah method displayPaths(int tujuan,

O

int awal) yang digunakan untuk menampilkan hasil yang berupa jarak terpendek bersama dengan jalur terpendek yang harus

SY

ST

ditempuh.

public int getMin() { double jarakTerpendek = INFINITE; int minIndeks = 0; for (int i = 1; i < jumlah_vertex; i++) {



bantu

=

new

DecimalFormat("#.###").format(sPath[tujuan].getJarak())+":"; while (tujuan != awal) {

+ "\n" + paths; tujuan

EM O

paths = daftarVertex[tujuan].getNama()

=

findIndex(daftarVertex[sPath[tujuan].getFrom()]

.getNama()); }

paths = daftarVertex[awal].getNama() + "\n" + paths; paths = bantu + paths; }

D

return paths; }

public String dijkstra(String awal, String tujuan) {

LS

int a = findIndex(awal); int b = findIndex(tujuan);

daftarVertex[a].setInGraph(true); jumGraph = 1;

for (int i = 0; i < jumlah_vertex; i++) {

O

double jarakSementara = edge[a][i]; sPath[i]

=

new

TemporaryJalur_n_Jarak(a,

jarakSementara); }

O

while (jumGraph < jumlah_vertex) {

double

minDist

sPath[minIndeks].getJarak();

ST

SY

int minIndeks = getMin();

if (minDist == INFINITE) { break; } else { vertSkrg = minIndeks;

=



int finish = findIndex(tujuan); String paths, bantu;

EM O

int[][] path = new int[jumlahHalte][jumlahHalte];

for (int i = 0; i < path.length; i++) {

for (int j = 0; j < path.length; j++) { if (jarak[i][j] == INFINITE) { path[i][j] = -1; } else { path[i][j] = i; } } }

path[i][i] = i; }

D

for (int i = 0; i < jumlahHalte; i++) {

for (int i = 0; i < jarak.length; i++) {

LS

for (int j = 0; j < jarak.length; j++) { for (int k = 0; k < jarak.length; k++) { if

jarak[j][k]) {

O

jarak[i][k];

(jarak[j][i]

+

jarak[i][k]

<

jarak[j][k]

=

jarak[j][i]

+

path[j][k] = path[i][k]; }

}

O

}

SY

ST

}

bantu

=

newDecimalFormat("#.###").format(jarak[start][finish])+":"; paths = daftarVertex[finish].getNama(); while (path[start][finish] != start) { paths

daftarVertex[path[start][finish]].getNama() + "\n" + paths;

=



public

List<String>

perpindahanBus2(StringTokenizer

stoken) { List<String> answer = new ArrayList<String>(); jalurPilihan

=

new

EM O

List<String> ArrayList<String>();

while (stoken.hasMoreElements()) {

jalurPilihan.add(stoken.nextToken("\n")); }

List daftarTrayek = new ArrayList(); for (int i = 0; i < jalurPilihan.size(); i++) {

int

awal

=

tujuan

=

D

if (i != 0) {

findIndex(jalurPilihan.get(i - 1)); int

LS

findIndex(jalurPilihan.get(i));

daftarTrayek.add(edgeTrayek[awal][tujuan]);

}

O

}

List<String> bantu = daftarTrayek.get(0); String baru = "";

O

String perpindahanHalte = "";

SY

ST

for (int i = 1; i < daftarTrayek.size(); i++) { baru = ""; for (int j = 0; j < bantu.size(); j++) { for

(int

k

=

0;

daftarTrayek.get(i).size(); k++) { if

(bantu.get(j).equals(daftarTrayek.get(i).get(k))) {

k

<



answer.add("Naik

bus

trayek:

"

+

bantu.get(i)); }

answer.add(perpindahanHalte); return answer; }

EM O

}

Gambar 4.3 Gambar Source Code untuk Perpindahan Bus

4.4.

Implementasi Penghitungan Running Time Sebuah Algoritma pada Kelas SitesOverlay

SitesOverlay

running

dengan

time

memanfaatkan

algoritma

dilakukan

pada

kelas

System.nanoTime()

yang

D

Penghitungan

syntax

LS

diletakkan di awal sebelum pemanggilan algoritma dan di akhir sesudah pemanggilan algoritma. Hal ini dilakukan untuk memeperoleh waktu mulai dan waktu selesai jalannya sebuah algoritma. Waktu selesai kemudian harus

O

dikurangi dengan waktu mulai agar mendapatkan lawa waktu yang diperlukan bagi sebuah algoritma untuk melakukan penghitungan. Lama waktu yang

O

didapat kemudian dibagi dengan satu juta untuk mendapatkan waktu dalam satuan milliseconds. Gambar 4.4 adalah gambar yang berisi source code untuk

SY

ST

penghitungan running time setiap algoritma yang digunakan dalam sistem.

startTime = System.nanoTime(); bantuToken

=

new

StringTokenizer(graph.dijkstra(awal[i],

tujuan[j]),":"); finishTime = System.nanoTime();



belakang, sedangkan tiga button digunakan untuk mengakses halaman peta dan Help. Gambar 4.5 adalah gambar dari hasil

EM O

halaman menu yang telah dibuat dan gambar 4.6 adalah source

LS

D

code yang digunakan untuk membuat halaman menu.

Gambar 4.5 Tampilan Halaman Menu

O

xmlns:android="http://schemas.android.com/apk/res/androi d"

SY

ST

O

android:layout_width="match_parent" android:layout_height="match_parent" >



menggunakan MapView dari Google yang telah diisi API Keynya. Pada halaman ini juga digunakan AutoCompleteTextView

dicari

oleh

menggunakan

pengguna. file

File xml

EM O

yang digunakan untuk menginputkan nama halte yang akan “activity_main.xml” lain

yang

juga

bernama

“mydropdownstyle.xml” yang digunakan untuk merubah warna text dan latar belakang pada AutoCompleteTextView yang

digunakan. Berikut ini adalah gambar 4.7, 4.8, dan 4.9 yang

D

merupakan tampilan dari halaman peta dan source code dari

SY

ST

O

O

LS

file xml dari “activity_main.xml” dan “mydropdownstyle.xml”.



android:layout_height="wrap_content" android:layout_alignParentBottom="true" android:layout_centerHorizontal="true"

EM O

android:text="@string/Detail" />

android:id="@+id/zoomControls1"

android:layout_width="wrap_content" android:layout_height="100dp"

android:layout_alignParentBottom="true" android:layout_centerHorizontal="true" android:orientation="vertical" >

D

android:id="@+id/editText1"

android:layout_width="wrap_content" android:layout_height="wrap_content" android:layout_alignParentLeft="true"

LS

android:layout_alignParentTop="true" android:layout_toLeftOf="@+id/button1" android:textColor="#000000" android:ems="10"

android:text="@string/empty" />

O

<requestFocus />

<Button

SY

ST

O

android:id="@+id/button1" android:layout_width="wrap_content" android:layout_height="wrap_content" android:layout_alignParentRight="true" android:layout_alignParentTop="true" android:text="@string/search" />

Gambar 4.8 activity_main.xml



EM O

100

D

Gambar 4.10 Tampilan Halaman Details AlertDialog.Builder

dialog

=

new

AlertDialog.Builder(context); by

"+

param

+

"

LS

dialog.setTitle("Details Algorithm");

dialog.setMessage("JARAK: "+ jarak + " km\nTIME ELAPSED: " + new DecimalFormat("#.###").format((finishTime startTime) / 1000000)

O

+ " ms\n-------"

+ "\nJALUR:\n" + paths + "\n-------\nSARAN:\n" + sarans);

SY

ST

O

dialog.setPositiveButton("OK", null); dialog.show();

Gambar 4.11 Source Code Halaman Details

4.5.4. Implementasi Halaman Help Tampilan halaman “Help” dibuat dengan membuat sebuah

file

xml

bernama

“help.xml”.

Halaman

ini



android:layout_width="match_parent" android:layout_height="match_parent" android:orientation="vertical" >

EM O

android:id="@+id/textView1"

android:layout_width="wrap_content"

android:layout_height="wrap_content" android:text="@string/howTo"

android:textAppearance="?android:attr/textAppearanceLarg e" />

D

android:id="@+id/imageView4"

android:layout_width="match_parent" android:layout_height="wrap_content" android:scaleType="center"

LS

android:src="@drawable/title_screen" />

android:id="@+id/textView17" android:layout_width="wrap_content" android:layout_height="wrap_content"

O

android:text="@string/judul"

android:textAppearance="?android:attr/textAppearanceMedi

SY

ST

O

um" />



android:layout_height="wrap_content" android:text="@string/menu3" />

EM O



android:layout_height="wrap_content"

android:text="@string/emptySource" />


android:layout_width="match_parent"

D

android:layout_height="170dp"

android:src="@drawable/map" />


LS

android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="@string/halamanMap"

android:textAppearance="?android:attr/textAppearanceMedi

SY

ST

O

O

um" />



android:layout_height="wrap_content" android:paddingLeft="15dp"

EM O

android:text="@string/cancelSource" />



android:layout_height="wrap_content"

android:text="@string/emptySource" />

android:layout_width="match_parent"

android:layout_height="wrap_content" >

D

android:id="@+id/textView7" android:layout_width="wrap_content" android:layout_height="wrap_content"

LS

android:text="@string/three" />

android:id="@+id/textView3" android:layout_width="wrap_content" android:layout_height="wrap_content" android:text="@string/howToAddDest"

SY

ST

O

O

/>



android:text="@string/pindahHalte" />

EM O



android:layout_height="wrap_content" android:paddingLeft="15dp"

android:src="@drawable/halte_change" />

D

SY

ST

O

O

LS

Gambar 4.13 help.xml



Membatalka Halte

bus

n titik awal.

ditentukan apakah titik awal apakah titik awal

telah

yang Muncul

pesan Muncul

sebagai titk awal akan sebelumnya. 3

titik tujuan.

dibatalkan akan dibatalkan

atau tidak.

Menentukan Halte bus yang ada Halte

bus

pada peta (selain disentuh

atau tidak.

yang Halte bus yang akan disentuh

yang telah ditandai ditandai sebagai titik awal).

pesan

EM O

2

akan

dengan ditandai dengan

ikon baru sebagai ikon

baru

titik tujuan.

titik

sebagai

Muncul garis pada tujuan.

yang Muncul

garis

D

peta

menghubungkan

pada peta yang

antar halte yang menghubungkan merupakan

jalur antar halte yang

LS

tempuh dari titik merupakan jalur awal

ke

titik tempuh dari titik

tujuan.

Melihat jalur yang

bus disentuh.

SY

ST

O

ditempuh.

5

Melihat nilai yang

terpendek harus

ke

titik

tujuan.

Tombol “Details” Rute

O

4

awal

jalur Rute

jalur

yang terpendek

yang

ditempuh harus

ditempuh

menggunakan bus menggunakan akan

muncul bus akan muncul

berupa poin-poin.

berupa

poin-

poin. Tombol “Details” Tampil total nilai Tampil total nilai

jarak disentuh.

jarak

terpendek jarak

terpendek

yang

harus yang

harus



RINGROAD

User diarahkan ke ke posisi halte

UTARA

posisi

(KENTUNGAN)

RINGROAD

UTARA

UTARA

(KENTUNGAN)

EM O

halte RINGROAD

(KENTUNGAN)

User

diarahkan

ke posisi halte

SUGIYONO

2 User diarahkan ke SUGIYONO

(MUSEUM

posisi

PERJUANGAN)

SUGIYONO (MUSEUM

2

halte (MUSEUM

2 PERJUANGAN)

9

Mencari

“”

halte.

D

PERJUANGAN) Tampil

pesan Tampil

pesan

bahwa halte yang bahwa

halte

LS

dicari

tidak yang dicari tidak diketahui.

diketahui.

SY

ST

O

O

TINUS

1

Menguji

Tampil

pesan Tampil

pesan

bahwa halte yang bahwa

halte

dicari

tidak yang dicari tidak diketahui.

diketahui.

SEMBARANG Tampil

Tampil

pesan

pesan bahwa

halte

bahwa halte yang yang dicari tidak dicari

tidak diketahui.

diketahui. Awal:

Jarak: 4,604 km

Dijkstra:



KOREM)

-SANATA

luaran

DHARMA

diharapkan.

-JL.

yang

COLOMBO

-JL.

EM O

(SAMIRONO)

COLOMBO

(PANTI RAPIH)

-CIK DI TIRO 1 (MUSEUM KOREM) Saran:

Awal:

MT Jarak: 4,299 km 2 Jalur:

dengan

(SMA 7)

-MT HARYONO luaran

yang

Tujuan:

2 (SMA 7)

TENTARA

-TEJOKUSUMAN

diharapkan.

PELAJAR 1 (SMP -NGABEAN

Floyd:

14)

-

Sama

dengan

COKROAMINOT

luaran

yang

O (SMA 1)

diharapkan.

O O ST

SY

Dijkstra: Sama

LS

HARYONO

D

Naik 2B.

-SMPN 11 -TENTARA PELAJAR 1 (SMP 14) Saran: Naik 3B – pindah ke 2B di Ngabean.

Tabel 5.1 Tabel Hasil Pengujian



public int getMin() { O(1)

int minIndeks = 0;

O(1)

EM O

double jarakTerpendek = INFINITE;

n

for (int i = 1; i < jumlah_vertex; i++) { if

(!daftarVertex[i].isInGraph()&&

sPath[i].getJarak() < jarakTerpendek){

jarakTerpendek = sPath[i].getJarak();

O(1)

minIndeks = i;

O(1)

} }

O(1)

return minIndeks; }

Berdasarkan

gambar

D

Gambar 5.1 Source Code Method getMin

5.1

method

getMin

memiliki

LS

kompleksitas waktu asimtotik O(n). Hal tersebut diperoleh melalui perhitungan berikut:

O(1)+O(1)+(n.(O(1)+O(1)))+ O(1)

O

O

= O(1)+O(1)+(n.O(1))+O(1) = O(1)+O(1)+O(n)+O(1) = O(n)

Gambar 5.2 adalah hasil penghitungan kompleksitas waktu

SY

ST

asimtotik tiap baris source code yang dimiliki oleh method adjust_sPath.

public void adjust_sPath() { int kolom = 0;

O(1)



bantu

=

new

DecimalFormat("#.###").format(sPath[tujuan].getJarak())+":";O(1) n

while (tujuan != awal) {

paths; O(1) tujuan

EM O

paths = daftarVertex[tujuan].getNama() + "\n" +

=

findIndex(daftarVertex[sPath[tujuan].getFrom()] .getNama());O(1) } paths

=

daftarVertex[awal].getNama()

paths; O(1) paths = bantu + paths; }

+

"\n"

+

O(1)

O(1)

return paths; }

D

Gambar 5.3 Source Code Method displayPaths

LS

Kompleksitas waktu asimtotik dari method displayPaths adalah:

O(1)+O(1)+(O(1)+(n.(O(1)+O(1)))+O(1)+O(1))+O(1) = O(1)+O(1)+(O(1)+O(n)+O(1)+O(1))+O(1)

O

O

= O(1)+O(1)+O(n)+O(1) = O(n)

SY

ST

public int findIndex(String index) { int a = 0;

O(1)

while (a < jumlah_vertex) {

n

if (index.equals(daftarVertex[a].getNama())) { return a; } else {

O(1)



sPath[i]

=

new

TemporaryJalur_n_Jarak(a, O(1)

jarakSementara); }

n

while (jumGraph < jumlah_vertex) {

double

O(n)

EM O

int minIndeks = getMin();

minDist

O(1)

sPath[minIndeks].getJarak();

=

if (minDist == INFINITE) { break; } else {

O(1)

vertSkrg = minIndeks; mulaiSmpSkrg sPath[minIndeks].getJarak();O(1) }

=

jumGraph++;

D

daftarVertex[vertSkrg].setInGraph(true);O(1)

adjust_sPath(); }

O(1) O(n)

O(1)

LS

jumGraph = 0; for (int i = 0; i < jumlah_vertex; i++) { daftarVertex[i].setInGraph(false);

n O(1)

}

return displayPaths(b, a);

O

}

O(n)

O

Gambar 5.5 Source Code Method dijkstra

Penghitungan kompleksitas waktu asimtotik algoritma

SY

ST

Dijkstra berdasarkan gambar 5.3 adalah O(n2). Penghitungan yang

dilakukan untuk memperoleh hasil tersebut adalah: O(n)+O(n)+O(1)+O(1)+(n.(O(1)+O(1)))+(n.(O(n)+O(1)+(O(1) +O(1))+O(1)+O(1)+O(n)))+O(1)+(n.O(1))+O(n) = O(n)+O(n)+O(1)+O(1)+O(n)+O(n2)+O(1)+O(n)+O(n)



Kompleksitas

waktu

asimtotik

untuk

method

findIndex

berdasarkan pada gambar 5.6 adalah O(1)+n.O(1)+O(1) = O(n).

EM O

Analisis hasil nilai Big Oh untuk setiap baris source code yang dimiliki oleh method deepCopyIntMatrix tertuang pada gambar 5.7

public static double[][] deepCopyIntMatrix(double[][] input) { if (input == null)

O(1)

return null;

O(1)

for (int r = 0; r < input.length; r++) {

n

D

double[][] result = new double[input.length][];

result[r] = input[r].clone(); }

O(1)

LS

return result; }

Gambar 5.7 Source Code Method deepCopyIntMatrix

O

Kompleksitas waktu asimtotik untuk method deepCopyMatrix berdasarkan pada gambar 5.7 adalah O(1) + O(1) + n.O(1) = O(n).

O

Setelah memperoleh nilai Big Oh dari method findIndex

dan deepCopyIntMatrix, penghitungan nilai Big Oh method floyd

SY

ST

dilakukan. Penghitungan nilai Big Oh dari method floyd dilakukan dengan melihat gambar 5.8.

public String floyd(String awal, String tujuan) { double[][] jarak = this.deepCopyIntMatrix(edge);O(n)



} paths = daftarVertex[start].getNama() + "\n" + paths; O(1) O(1)

paths = bantu + paths; return paths;

EM O

O(1) }

Gambar 5.8 Source Code Method Floyd

Dengan menggunakan gambar 5.8, penghitungan kompleksitas waktu asimtotik dari algoritma Floyd-Warshall adalah:

O(n)+O(n)+O(n)+O(1)+(n.(n.(O(1)+O(1))))+(n.O(1))+(n.O(1))+(n

D

.(n.(n.((O(1)+O(1))))))+O(1)+O(1)+n.(O(1)+O(1))+O(1)+O(1)+O (1)

LS

=

O(n)+O(n)+O(n)+O(1)+O(n2)+O(n)+O(n)+O(n3)+O(1)+O(n)+O(1 ))+O(1)+O(1)+O(1)

5.3.

O

= O(n3)

Pengujian dan Analisa Hasil Perbandingan Running Time Algoritma

O

Dijkstra dan Floyd-Warshall Pengujian running time masing-masing algoritma dilakukan dengan

SY

ST

menggunakan sepuluh kasus. Pengujian direpresentasikan melalui tabel 5.2. Kolom pertama adalah nomor uji, kolom kedua merupakan titik awal, kolom kedua merupakan titik tujuan, kolom keempat merupakan running time algoritma Dijkstra, dan kolom terakhir merupakan running time algoritma



UTARA (INSTIPER (TAMAN 1/INSTIPER 2)

PINTAR/TAMAN

6.

TERMINAL

EM O

SENOPATI) GIWANGAN

16 ms

CONDONGCATUR SUDIRMAN

3 JL.

(GONDOLAYU) 8.

COLOMBO 9 ms

(KOSUDGAMA)

MT HARYONO 2 RINGROAD (SMA 7)

UTARA (INSTIPER

9 ms

220 ms

222 ms

D

7.

233 ms

9.

LS

1/INSTIPER 2) MANGKUBUMI (TUGU)

1 AHMAD

YANI 8 ms

222 ms

(BENTENG

VREDEBURG)

MT HARYONO 2 KATAMSO

O

10

225 ms

(IMMACULATA)

O

(SMA 7)

2 9 ms

SY

ST

Tabel 5.2 Tabel Hasil Pengujian Running Time Kedua Algoritma

Berdasarkan tabel 5.2, dari sepuluh kasus yang diberikan, algoritma

Dijkstra mampu memberikan solusi lebih cepat dari algoritma FloydWarshall untuk semua kasus yang diberikan. Hal tersebut dikarenakan algoritma Dijkstra mempunyai kompleksitas waktu asimtotik (Big Oh) yang



BAB VI

EM O

KESIMPULAN DAN SARAN Pada bab ini akan dibahas mengenai kesimpulan dan saran dari penelitian yang telah dibuat. 6.1.

Kesimpulan

Kesimpulan dari penelitian yang telah dilakukan adalah:

1. Penggunaan metode greedy dan metode pemrograman dinamis yang

D

masing-masing diwakili oleh algoritma Dijkstra dan Floyd-Warshall mampu memberikan solusi yang tepat pada kasus pencarian jalur terpendek pada Bus Trans Jogja. Dijkstra

dan

algoritma

LS

2. Algoritma

Floyd-Warshall

mampu

diimplementasikan dalam sistem pencarian jalur terpendek untuk kasus Bus Trans Jogja karena mampu memberikan solusi jalur terpendek yang

O

tepat.

3. Running time dari algoritma Dijkstra lebih cepat daripada running time

O

dari algoritma Floyd-Warshall dalam memberikan solusi kepada pengguna. Hal tersebut juga Nampak pada kompleksitas waktu asimtotik

SY

ST

dari algoritma Dijkstra yang lebih sederhana, yakni O(n2) dibandingkan

dengan kompleksitas waktu asimtotik dari algoritma Floyd-Warshall yang adalah O(n3).

128



DAFTAR PUSTAKA

EM O

Arifianto, Sofyan. (2012). Sistem Aplikasi Penentuan Rute Terpendek Pada Jaringan Multi Moda Transportas Umum Menggunakan Algoritma Dijkstra. Tesis S-2 pada Universitas Diponegoro Semarang: tidak diterbitkan.

Bell, Donalds. (2004). UML Basics: The Class Diagram. Online. Tersedia: http://www.ibm.com/developerworks/rational/library/content/RationalEdge/se

D

p04/bell/. 28 Mei 2013.

LS

Bell, Rob. (2009). A Beginner’s Guide to Big O Notation. Online. Tersedia: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/. 5 Juni 2013. Cooper, Leon dan Mary W. Cooper. (1981). Introduction to Dynammic

O

Programming. Dallas: Pergamon Press.

O

Denardo, Eric V. (2003). Dynamic Programming Models and Applications.

SY

ST

New York: Dover Publications, Inc.

Fanani, Lutfi. (2012). Rancang Bangun Aplikasi Web Pencarian Rute Terpendek Antar Gedung di Kampus Menggunakan Algoritma FloydWarshall. Journal Basic Science And Technology. 1(3), 7-11.

130



LAMPIRAN

LS

D

EM O

Lampiran 1: User Manual

1. Sentuh tombol “Algoritma Dijkstra” untuk masuk ke halaman “Map” dan kemudian melakukan pencarian jalur terpendek dengan menggunakan algoritma Dijkstra.

2. Sentuh tombol “Algoritma Floyd-W” untuk masuk ke halaman “Map” dan

O

kemudian melakukan pencarian jalur terpendek dengan menggunakan algoritma Floyd-Warshall.

O

3. Sentuh tombol “Help” untuk masuk ke halaman “Help” yang berisi cara

SY

ST

penggunaan sistem.

132



SY

ST

O

O

LS

D

EM O

Lampiran 2: Gambar Peta Jalur dan Halte Bus Trans Jogja



SY

ST

O

O

D

LS

RINGROAD UTARA (MONJALI 2) RINGROAD UTARA (STIKES GUNA BANGSA) RINGROAD UTARA (UPN) RS AU DR. S. HARDJOLUKITO RS DR YAP RSI HIDAYATULAH RSUP DR. SARDJITO SANATA DHARMA SANTREN SENOPATI 1 (TAMAN SENOPATI) SENOPATI 2 (TAMAN PINTAR) SMP 5 YOGYAKARTA SMPN 11 SOROGENEN (NITIKAN) SOROGENEN (WIROSABAN) SUDIRMAN 2 (BUMI PUTERA) SUDIRMAN 3 (GONDOLAYU) SUDRIMAN 1 (BETHESDA) SUGIYONO 1 (SD PUJOKUSUMAN) SUGIYONO 2 (MUSEUM PERJUANGAN) SUSTERAN NOVISIAT TEGAL GENDU 1 TEGAL GENDU 2 TEGALTURI 1 TEGALTURI 2 TEJOKUSUMAN TENTARA PELAJAR 1 (SMP 14) TENTARA PELAJAR 2 (SAMSAT) TERMINAL CONDONGCATUR TERMINAL JOMBOR UNY URIP SUMOHARJO (LPP)

EM O

136


EM


D

TENTARA PELAJAR 1 (SMP 14) JL. COLOMBO (KOSUDGAMA) JL. SOLO (DE BRITTO) JL. SOLO (AMBARUKMO) JANTI FLYOVER JL. SOLO (JANTI) AM. SANGAJI 2 (JETIS) MANGKUBUMI 1 (TUGU) KATAMSO 1 (PURAWISATA) SUGIYONO 1 (SD PUJOKUSUMAN) RSI HIDAYATULAH NGEKSIGONDO (DIKLAT PU) GEDONG KUNING (DEP.KEHUTANAN) KUSUMANEGARA (GEMBIRALOKA) KUSUMANEGARA 4 (SGM) KENARI 2 (MANDALA KRIDA) SMP 5 YOGYAKARTA SUDRIMAN 1 (BETHESDA) RS DR YAP JL. COLOMBO (KOSUDGAMA) JL. COLOMBO (UNY) UNY SANTREN TERMINAL CONDONGCATUR RINGROAD UTARA (MONJALI 2) RINGROAD UTARA (MONJALI 1)

SY

ST O

O

LS

SENOPATI 1 (TAMAN SENOPATI) RS DR YAP JL. COLOMBO (UNY) JL. SOLO (DE BRITTO) JL. SOLO (AMBARUKMO) JANTI FLYOVER RINGROAD UTARA (MONJALI 1) AM. SANGAJI 2 (JETIS) SENOPATI 2 (TAMAN PINTAR) KATAMSO 1 (PURAWISATA) SUGIYONO 1 (SD PUJOKUSUMAN) RSI HIDAYATULAH NGEKSIGONDO (DIKLAT PU) GEDONG KUNING (DEP.KEHUTANAN) KUSUMANEGARA (GEMBIRALOKA) KUSUMANEGARA 4 (SGM) KENARI 2 (MANDALA KRIDA) SMP 5 YOGYAKARTA SUDRIMAN 1 (BETHESDA) RS DR YAP JL. COLOMBO (KOSUDGAMA) JL. COLOMBO (UNY) UNY SANTREN RINGROAD UTARA (MANGGUNG TERMINAL JOMBOR

2.84 0.905 1.47 0.941 1.16 0.611 3.155 0.999 0.981 0.791 1.984 1.302 0.764 2.27 0.598 1.676 2.601 0.981 0.533 0.905 0.916 0.512 0.958 1.249 2.198 0.949

1B 1B 1B 1B 1B 1B 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2B

1B

1B

2A


EM


D

GEDONG KUNING (JEC) JL. SOLO (JANTI) JL. SOLO (ALFA) JL. SOLO (MAGUWO) BANDARA ADISUCIPTO RINGROAD UTARA (DISNAKER) RINGROAD UTARA (INSTIPER 2) RINGROAD UTARA (UPN) TERMINAL CONDONGCATUR RINGROAD UTARA (MANGGUNG) FK-UGM JL. KALIURANG (KOPMA UGM) CIK DI TIRO 1 (MUSEUM KOREM) KOTABARU SUDIRMAN 2 (BUMI PUTERA) DIPONEGORO TENTARA PELAJAR 2 (SAMSAT) JLAGRAN MALIOBORO 1 (GARUDA) MALIOBORO 2 (KEPATIHAN) AHMAD YANI (BENTENG VREDEBURG) KHA DAHLAN 1 (PAPPMI) MT HARYONO 1 (JOKTENG) SUGIYONO 1 (SD PUJOKUSUMAN) LOWANU SOROGENEN (WIROSABAN)

SY

ST O

O

LS

GEDONG KUNING (DEP.KEHUTANAN) GEDONG KUNING (JEC) JL. SOLO (JANTI) JL. SOLO (ALFA) JL. SOLO (MAGUWO) BANDARA ADISUCIPTO RINGROAD UTARA (DISNAKER) RINGROAD UTARA (INSTIPER 2) RINGROAD UTARA (UPN) TERMINAL CONDONGCATUR RINGROAD UTARA (MANGGUNG) FK-UGM JL. KALIURANG (KOPMA UGM) SMP 5 YOGYAKARTA KOTABARU SUDIRMAN 2 (BUMI PUTERA) DIPONEGORO TENTARA PELAJAR 2 (SAMSAT) JLAGRAN MALIOBORO 1 (GARUDA) MALIOBORO 2 (KEPATIHAN) AHMAD YANI (BENTENG VREDEBURG) NGABEAN MT HARYONO 1 (JOKTENG) SUGIYONO 1 (SD PUJOKUSUMAN) LOWANU

2.395 2.566 0.902 0.905 1.071 2.966 1.17 1.774 1.612 1.381 2.467 0.991 1.128 0.819 0.383 0.773 0.678 0.692 1.138 0.492 0.517 0.668 1.182 1.416 1.132 0.662

3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A 3A

1A 1A 1A 1A

1B 1B 1B

2A

1A 1A

2A 2A

3B


EM


TEGAL GENDU 1 GEDONG KUNING (BANGUNTAPAN) GIWANGAN

SY

ST O

O

LS

D

GEDONG KUNING (BANGUNTAPAN) GEDONG KUNING (WONOCATUR) TEGAL GENDU 1

3.201 3B 1.411 3B 1.412 3B


EM


JL. SOLO (DE BRITTO)

-7.782995

110.394005

JL. SOLO (GEDUNG WANITA)

JL. SOLO (GEDUNG WANITA)

-7.783346

110.393972

JL. SOLO (JANTI)

JL. SOLO (JANTI)

-7.783101

110.411439

JL. SOLO (KALASAN)

JL. SOLO (KALASAN)

-7.75981

110.477357

JL. SOLO (KR.1)

JL. SOLO (KR.1)

-7.766571

110.472465

JL. SOLO (KR.2)

JL. SOLO (KR.2)

-7.775458

110.461006

JL. SOLO (MAGUWO)

JL. SOLO (MAGUWO)

-7.783176

110.430729

JLAGRAN

JLAGRAN

-7.789505

110.360195

KARANGJATI

-7.757004

110.369468

KATAMSO 1 (PURAWISATA)

-7.809835

110.369318

KATAMSO 2 (IMMACULATA)

KATAMSO 2 (IMMACULATA)

-7.803011

110.368974

KENARI 1/KENARI 2 (MANDALA KRIDA)

KENARI 1 (MANDALA KRIDA);KENARI 2 (MANDALA KRIDA)

-7.797541

110.383836

KHA DAHLAN (PAPPMI/NGADIWINATAN)

KHA DAHLAN 1 (PAPPMI);KHA DAHLAN 2 (NGADIWINATAN)

-7.80119

110.358703

KOTABARU

KOTABARU

-7.784524

110.371334

KUSUMANEGARA (GEDUNG JUANG 45)

KUSUMANEGARA (GEDUNG JUANG 45)

-7.802283

110.400589

KUSUMANEGARA (GEMBIRALOKA)

KUSUMANEGARA (GEMBIRALOKA)

-7.802325

110.398715

KUSUMANEGARA (SGM)

KUSUMANEGARA 3 (SGM);KUSUMANEGARA 4 (SGM)

-7.802144

110.393551

KUSUMANEGARA 1 (TMP)

KUSUMANEGARA 1 (TMP)

-7.801865

110.383544

KUSUMANEGARA 2 (STPP)

KUSUMANEGARA 2 (STPP)

-7.801868

110.381746

LOWANU

LOWANU

-7.823185

110.378072

MALIOBORO 1 (GARUDA)

MALIOBORO 1 (GARUDA)

-7.790999

110.366142

MALIOBORO 2 (KEPATIHAN)

MALIOBORO 2 (KEPATIHAN)

-7.794975

110.365648

SY

ST O

O

KATAMSO 1 (PURAWISATA)

LS

KARANGJATI

D

JL. SOLO (DE BRITTO)


RS DR YAP

RS DR YAP

110.375036

RSI HIDAYATULAH

RSI HIDAYATULAH

-7.815511

110.387803

RSUP DR. SARDJITO

RSUP DR. SARDJITO

-7.770118

110.373346

SENOPATI (TAMAN PINTAR/TAMAN SENOPATI)

SENOPATI 2 (TAMAN PINTAR);SENOPATI 1 (TAMAN SENOPATI)

-7.801523

110.367655

SMP 5 YOGYAKARTA

SMP 5 YOGYAKARTA

-7.787327

110.375353

SMPN 11

SMPN 11

-7.793417

110.353187

SOROGENEN (NITIKAN)

SOROGENEN (NITIKAN)

-7.824928

110.379467

SOROGENEN (WIROSABAN)

-7.824673

110.379499

SUDIRMAN 2 (BUMI PUTERA)

SUDIRMAN 2 (BUMI PUTERA)

-7.783112

110.369425

SUDIRMAN 3 (GONDOLAYU)

SUDIRMAN 3 (GONDOLAYU)

-7.782708

110.369017

SUDRIMAN 1 (BETHESDA)

SUDRIMAN 1 (BETHESDA)

-7.783154

110.377847

SUGIYONO 1 (SD PUJOKUSUMAN)

SUGIYONO 1 (SD PUJOKUSUMAN)

-7.814697

110.369077

SUGIYONO 2 (MUSEUM PERJUANGAN)

SUGIYONO 2 (MUSEUM PERJUANGAN)

-7.814921

110.370215

SUSTERAN NOVISIAT/SANTREN

SUSTERAN NOVISIAT;SANTREN

-7.766008

110.392159

TEGAL GENDU 1

TEGAL GENDU 1

-7.825614

110.391296

TEGAL GENDU 2

TEGAL GENDU 2

-7.825513

110.391215

TEGALTURI 1

TEGALTURI 1

-7.825821

110.388458

TEGALTURI 2

TEGALTURI 2

-7.82547

110.388082

TEJOKUSUMAN

TEJOKUSUMAN

-7.807858

110.355949

TENTARA PELAJAR 1 (SMP 14)

TENTARA PELAJAR 1 (SMP 14)

-7.786365

110.359812

TENTARA PELAJAR 2 (SAMSAT)

TENTARA PELAJAR 2 (SAMSAT)

-7.78713

110.359941

TERMINAL CONDONGCATUR

TERMINAL CONDONGCATUR

-7.757684

110.39556

TERMINAL JOMBOR

TERMINAL JOMBOR

-7.747478

110.362086

SY

ST O

O

SOROGENEN (WIROSABAN)

LS

-7.78105

D

146

EM




Lampiran 6: Source Code Kelas Graph package com.entity; java.text.DecimalFormat; java.util.ArrayList; java.util.List; java.util.StringTokenizer;

EM O

import import import import

D

public class Graph { private final int INFINITE = 1000000; double edge[][]; ArrayList<String> edgeTrayek[][]; Halte daftarVertex[]; int jumlah_vertex, jumlahHalte; int jumGraph; int vertSkrg; double mulaiSmpSkrg; TemporaryJalur_n_Jarak sPath[];

new

O

LS

public Graph(int jumlahHalte) { this.jumlahHalte = jumlahHalte; edge = new double[jumlahHalte][jumlahHalte]; edgeTrayek = ArrayList[jumlahHalte][jumlahHalte]; daftarVertex = new Halte[jumlahHalte]; jumlah_vertex = 0; jumGraph = 0; for (int i = 0; i < jumlahHalte; i++) { for (int j = 0; j < jumlahHalte; j++) { edge[i][j] = INFINITE; edgeTrayek[i][j] = null; } } sPath = new TemporaryJalur_n_Jarak[112]; }

SY

ST

O

public void insertHalte(String vortex) { Halte a = new Halte(vortex); daftarVertex[jumlah_vertex] = a; jumlah_vertex++; }

public nilai,

void

insertJarak(String

a,

String

ArrayList<String> trayek) { int x = findIndex(a); int y = findIndex(b); if (x != -1 && y != -1) { edge[x][y] = nilai;

b,

double



EM O

String paths = ""; String bantu = ""; if (sPath[tujuan].getJarak() != INFINITE) { // paths.push(String.valueOf(sPath[tujuan].getJarak()));

D

bantu = new DecimalFormat("#.###").format(sPath[tujuan].getJarak())+":";// String.valueOf(sPath[tujuan].getJarak()) + ":"; while (tujuan != awal) { // /paths.push(daftarVertex[tujuan].getNama()); paths = daftarVertex[tujuan].getNama() + "\n" + paths; tujuan = findIndex(daftarVertex[sPath[tujuan].getFrom()] .getNama()); } paths = daftarVertex[awal].getNama() + "\n" + paths; paths = bantu + paths; // paths.push(daftarVertex[awal].getNama()); } return paths;

LS

}

SY

ST

O

O

public String dijkstra(String awal, String tujuan) { int a = findIndex(awal); int b = findIndex(tujuan); daftarVertex[a].setInGraph(true); jumGraph = 1; for (int i = 0; i < jumlah_vertex; i++) { double jarakSementara = edge[a][i]; sPath[i] = new TemporaryJalur_n_Jarak(a, jarakSementara); } while (jumGraph < jumlah_vertex) { int minIndeks = getMin(); double minDist = sPath[minIndeks].getJarak(); if (minDist == INFINITE) { break; } else { vertSkrg = minIndeks; mulaiSmpSkrg = sPath[minIndeks].getJarak(); } daftarVertex[vertSkrg].setInGraph(true); jumGraph++; adjust_sPath(); }



paths

=

daftarVertex[start].getNama()

+

"\n"

+

paths; paths = bantu + paths; return paths;

EM O

} public static double[][] deepCopyIntMatrix(double[][] input) { if (input == null) return null; double[][] result = new double[input.length][]; for (int r = 0; r < input.length; r++) { result[r] = input[r].clone(); } return result; }

D

public List<String> perpindahanBus2(StringTokenizer stoken) { List<String> answer = new ArrayList<String>(); List<String> jalurPilihan = new ArrayList<String>();

LS

while (stoken.hasMoreElements()) { jalurPilihan.add(stoken.nextToken("\n")); }

= =

O

List daftarTrayek = new ArrayList(); for (int i = 0; i < jalurPilihan.size(); i++) { if (i != 0) { int awal findIndex(jalurPilihan.get(i - 1)); int tujuan findIndex(jalurPilihan.get(i)); daftarTrayek.add(edgeTrayek[awal][tujuan]); }

O

}

List<String> bantu = daftarTrayek.get(0); String baru = ""; String perpindahanHalte = "";

SY

ST

for (int i = 1; i < daftarTrayek.size(); i++) { baru = ""; for (int j = 0; j < bantu.size(); j++) { for (int k = 0; k daftarTrayek.get(i).size(); k++) { if (bantu.get(j).equals(daftarTrayek.get(i).get(k))) {

<



private boolean isInGraph;

public void setNama(String nama) { this.nama = nama; } public boolean isInGraph() { return isInGraph; }

EM O

public String getNama() { return nama; }

public void setInGraph(boolean isInGraph) { this.isInGraph = isInGraph; }

D

public Halte(String nama) { this.nama = nama; this.isInGraph = false; } }

LS

Lampiran 8: Source Code Kelas TemporaryJalur_n_Jarak package com.entity;

public class TemporaryJalur_n_Jarak { private double jarak; private int from;

O

public double getJarak() { return jarak; }

SY

ST

O

public void setJarak(double jarak) { this.jarak = jarak; } public int getFrom() { return from; } public void setFrom(int from) { this.from = from; } public TemporaryJalur_n_Jarak(int from, double jarak) { super();



Point p1 = new Point(); Point p2 = new Point();

path2.moveTo(p2.x, p2.y); path2.lineTo(p1.x, p1.y);

EM O

Path path2 = new Path(); projection.toPixels(ppoint.get(i), p1); projection.toPixels(ppoint.get(i-1), p2);

canvas.drawPath(path2, mPaint); } return false; }

D

}

Lampiran 10: Source Code Kelas SitesOverlay package com.view; java.text.DecimalFormat; java.util.ArrayList; java.util.List; java.util.StringTokenizer;

import import import import import import import import import

android.app.AlertDialog; android.content.Context; android.content.DialogInterface; android.content.DialogInterface.OnClickListener; android.graphics.Canvas; android.graphics.drawable.Drawable; android.view.View; android.widget.Button; android.widget.Toast;

O

O

LS


SY

ST

import import import import import import

com.entity.Graph; com.google.android.maps.GeoPoint; com.google.android.maps.ItemizedOverlay; com.google.android.maps.MapView; com.google.android.maps.OverlayItem; com.google.android.maps.Projection;

public class SitesOverlay extends ItemizedOverlay { private List items = new ArrayList();



public void draw(Canvas canvas, MapView mapView, boolean shadow) { super.draw(canvas, mapView, shadow); boundCenterBottom(marker);

EM O

} public void addItem(OverlayItem item) { items.add(item); populate(); } public void addFlag(int[] itemSize) { this.itemSize = itemSize; }

protected boolean onTap(final int i) {

if (items.get(i).getTitle().equals("Lokasi Anda")) {

D

Toast.makeText(context, items.get(i).getTitle(), Toast.LENGTH_SHORT) .show(); } else {

O

LS

if (itemSize[i] == 0) { AlertDialog.Builder dialog AlertDialog.Builder(context); z = items.get(i).getTitle();

=

new

dialog.setTitle(z); if (status == 0) { dialog.setMessage("Halte awal"); x = items.get(i).getSnippet(); } else { dialog.setMessage("Halte

O

tujuan?");

y = items.get(i).getSnippet(); } dialog.setNegativeButton("Tidak",

new

OnClickListener() {

SY

ST

@Override public void onClick(DialogInterface dialog, int which) { // TODO Auto-generated method stub dialog.dismiss(); itemSize[i] = 0; } });



items.get(i).setMarker(markerEnd); boundCenterBottom(markerEnd); mapView.invalidate();

EM O

buttonDetails.setVisibility(View.GONE); } else { counter2 = i; ArrayList geoPoints = new ArrayList(); status = 0;

String[] new String[2];

results

=

StringTokenizer stoken, stokenAwal, stokenTujuan, bantuToken; =

D

stokenAwal

StringTokenizer(x, ";");

new

String[] awal = new

String[stokenAwal.countTokens()];

for (int i = 0; i <

String();

LS

awal.length; i++) { awal[i]

=

new

awal[i]

=

stokenAwal.nextToken();

} stokenTujuan

=

new

StringTokenizer(y, ";");

String[]

tujuan

=

O

new String[stokenTujuan .countTokens()];

for (int i = 0; i <

O

tujuan.length; i++) {

tujuan[i]

=

tujuan[i]

=

new String();

SY

ST

stokenTujuan.nextToken(); } double

bantuJarak

=

-1;

if

(param.equals("DIJKSTRA")) { 0; i < awal.length; i++) {

for

(int

i

=



for

(int

i

=

0; i < awal.length; i++) { for

(int

j = 0; j < tujuan.length; j++) {

EM O

startTime = System.nanoTime(); bantuToken = new StringTokenizer(graph .floyd(awal[i], tujuan[j]), ":");

finishTime = System.nanoTime(); String jarak=bantuToken.nextToken(); jalur=bantuToken.nextToken(); if (bantuJarak == -1) { bantuJarak = Double.parseDouble(jarak);

results[0] = String

D

stoken = bantuToken;

.valueOf(bantuJarak); results[1] = jalur;

}

LS

else {

if (bantuJarak > Double

.parseDouble(jarak)) {

O

bantuJarak = Double

.parseDouble(jarak);

stoken = bantuToken;

O

results[0] = String .valueOf(bantuJarak);

SY

ST

results[1] = jalur;

} } } } }



if (bantu.equals(items.get(i).getTitle())) { items.get(i).setMarker(markerChange);

EM O

boundCenterBottom(markerChange); counter3 = i;

}

}

}

String saran = ""; for (int i = 0; i < trayeks.size() - 1; i++) {

saran

+ trayeks.get(i) + "\n";

=

saran

}

final String paths =

D

path;

final String jarak =

results[0];

final

String

sarans

LS

= saran;

buttonDetails.setVisibility(View.VISIBLE); buttonDetails .setOnClickListener(new View.OnClickListener() { @Override

O

public void onClick(View v) {

// TODO Auto-generated method stub

O

AlertDialog.Builder dialog = new AlertDialog.Builder( context);

SY

ST

dialog.setTitle("Details by " + param + " Algorithm");

dialog.setMessage("JARAK: " + jarak + " km\nTIME ELAPSED: "



EM O

@Override public void onClick(DialogInterface dialog, int which) { // TODO Auto-generated method stub dialog.dismiss(); } }); dialog.show(); } } return true; } }

package com.example.skripsi; import android.app.Activity; import android.os.Bundle;

D

Lampiran 11: Source Code Kelas Help

O

}

LS

public class Help extends Activity { @Override public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.help);

O

@Override public void onBackPressed() { // TODO Auto-generated method stub finish(); System.exit(0); super.onBackPressed(); }

SY

ST

}

Lampiran 12: Source Code Kelas MainActivity package com.example.skripsi; import android.app.Activity; import android.content.Intent;



} }); }

EM O

}

Lampiran 13: Source Code Kelas Map package com.example.skripsi; java.io.IOException; java.io.InputStream; java.util.ArrayList; java.util.List;

import import import import import import import import import import import import import import import import import

jxl.Sheet; jxl.Workbook; jxl.read.biff.BiffException; android.app.AlertDialog; android.content.Context; android.graphics.drawable.Drawable; android.location.Criteria; android.location.Location; android.location.LocationListener; android.location.LocationManager; android.os.Bundle; android.view.Menu; android.view.View; android.widget.ArrayAdapter; android.widget.AutoCompleteTextView; android.widget.Button; android.widget.LinearLayout;

import import import import import import import import import import

com.entity.Graph; com.google.android.maps.GeoPoint; com.google.android.maps.MapActivity; com.google.android.maps.MapController; com.google.android.maps.MapView; com.google.android.maps.MapView.LayoutParams; com.google.android.maps.MyLocationOverlay; com.google.android.maps.Overlay; com.google.android.maps.OverlayItem; com.view.SitesOverlay;

SY

ST

O

O

LS

D


public class Map extends MapActivity { MapView mapView = null; MyLocationOverlay me = null; MapController mapController; SitesOverlay sitesOverlays, sitesOverlay2; Graph graph; Button buttonDetails;



for sheet2.getColumns(); i++) {

(int

i

=

3;

i

<

trayek.add(sheet2.getCell(i, j).getContents());

D

EM O

} graph.insertJarak(sheet2.getCell(0, j).getContents(), sheet2 .getCell(1, j).getContents(), Double.parseDouble(sheet2 .getCell(2, j).getContents()), trayek); } } catch (BiffException e) { e.printStackTrace(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } autoText = (AutoCompleteTextView) findViewById(R.id.editText1); ArrayAdapter<String> adapter = new ArrayAdapter<String>(this, R.layout.mydropdownstyle, namaHalte); autoText.setThreshold(1); autoText.setAdapter(adapter);

LS

Button cariButton = findViewById(R.id.button1); cariButton.setOnClickListener(new View.OnClickListener() {

(Button)

O

O

@Override public void onClick(View v) { // TODO Auto-generated method stub int flag = -1; for (int i = 0; i sitesOverlay2.size(); i++) { if (sitesOverlay2.getItem(i).getTitle()

SY

ST

.equalsIgnoreCase(autoText.getText().toString())) { flag = 1; mapController.animateTo(sitesOverlay2.getItem(i) .getPoint()); autoText.setText(""); break; } } System.out.println(flag); if (flag == -1) {

<



Drawable iconChangeHalte getResources().getDrawable( R.drawable.halte_change);

=

SitesOverlay(iconHalte, Map.this,

mapView,

D

sitesOverlay2 = new iconStart, iconEnd, graph, buttonDetails, param, iconChangeHalte);

EM O

iconHalte.setBounds(0, 0, iconHalte.getIntrinsicWidth(), iconHalte.getIntrinsicHeight()); iconStart.setBounds(0, 0, iconStart.getIntrinsicWidth(), iconStart.getIntrinsicHeight()); iconEnd.setBounds(0, 0, iconEnd.getIntrinsicWidth(), iconEnd.getIntrinsicHeight()); iconChangeHalte.setBounds(0, 0, iconChangeHalte.getIntrinsicWidth(), iconChangeHalte.getIntrinsicHeight());

=

=

new

new

O

LS

for (int j = 0; j < sheet3.getRows(); j++) { Double latitudeHalte1 Double.parseDouble(sheet3.getCell(2, j) .getContents()) * 1E6; Double longitudeHalte1 Double.parseDouble(sheet3.getCell(3, j) .getContents()) * 1E6; GeoPoint pointHalte1 = GeoPoint(latitudeHalte1.intValue(), longitudeHalte1.intValue()); OverlayItem halte1 = OverlayItem(pointHalte1, sheet3.getCell(0, j).getContents(), sheet3.getCell(1, j).getContents()); sitesOverlay2.addItem(halte1); }

SY

ST

O

int[] items = new int[sitesOverlay2.size()]; for (int i = 0; i < items.length; i++) { items[i] = 0; } sitesOverlay2.addFlag(items); overlays = mapView.getOverlays(); overlays.add(sitesOverlay2);

String provider locationManager.getBestProvider(criteria, true);

=



EM O

Overlay bantu2=null; // System.out.println(overlays.get(0); if (overlays.size() == 2) { overlays.remove(1); overlays.add(sitesOverlays); } else if (overlays.size() == 3) { bantu = overlays.get(2); overlays.remove(2); overlays.remove(1); overlays.add(sitesOverlays); overlays.add(bantu); } else { overlays.add(sitesOverlays); } mapController.animateTo(myPoint); System.out.println(overlays.size()); } }

locationListener

D

private final LocationListener LocationListener() {

=

}

int

LS

@Override public void onStatusChanged(String provider, status, Bundle extras) { // TODO Auto-generated method stub

new

@Override public void onProviderEnabled(String provider) { // TODO Auto-generated method stub

O

}

SY

ST

O

@Override public void onProviderDisabled(String provider) { // TODO Auto-generated method stub updateNewLocation(null); } @Override public void onLocationChanged(Location location) { // TODO Auto-generated method stub updateNewLocation(location); }

}; @Override protected boolean isRouteDisplayed() { // TODO Auto-generated method stub


PERBANDINGAN PENGGUNAAN ALGORITMA DIJKSTRA DAN ALGORITMA FLOYD-WARSHALL UNTUK PENCARIAN JALUR TERPENDEK PADA BUS TRANS JOGJA

Recommend Documents