IMPLEMENTASIALGORITMAFLOYD WARSHALL DALAM MENENTUKAN JARAK TERPENDEK (MEDAN - BANDARA KUALA NAMU)
SKRIPSI
RINI CHAIRANI HARAHAP 121421090
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
IMPLEMENTASI ALGORITMA FLOYD WARSHALL DALAM MENENTUKAN JARAK TERPENDEK (MEDAN - BANDARA KUALA NAMU) SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer
RINI CHAIRANI HARAHAP 121421090
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
ii PERSETUJUAN
Judul
Kategori
: IMPLEMENTASI ALGORITMA FLOYDWARSHALL DALAM MENENTUKAN JARAK TERPENDEK (MEDAN - BANDARA KUALA NAMU) : SKRIPSI
Nama
: RINI CHAIRANI HARAHAP
Nomor Induk Mahasiswa : 121421090 Program Studi
: EKSTENSI S1 ILMU KOMPUTER
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Pembimbing II
Pembimbing I
Dr. Syahril Efendi, SSi, MIT. NIP.196711101996021001
Dian Rachmawati, S.Si, M.Kom NIP. 198307232009122004
Diketahui/disetujui oleh Program Studi Ekstensi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 19620217 199103 1 001
Universitas Sumatera Utara
iii PERNYATAAN
IMPLEMENTASI ALGORITMA FLOYD WARSHALL DALAM MENENTUKAN JARAK TERPENDEK (MEDAN - BANDARA KUALA NAMU)
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
September 2015
Rini Chairani Harahap NIM. 121421090
Universitas Sumatera Utara
iv PENGHARGAAN
Bismillahirrohmanirrohim
Segala puji dan syukur penulis ucapkan kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya kepada penulis sehingga dapat menyelesaikan skripsi ini tepat waktu sesuai dengan instruksi dan peraturan yang berlaku di Fakultas Ilmu Komputer dan Teknologi Informasi serta shalawat dan salam penulis hadiahkan kepada Nabi Besar Muhammad SAW.
Dalam penyusunan dan penulisan skripsi ini, penulis banyak mendapat bantuan, dukungan, dan bimbingan dari berbagai pihak. Pada kesempatan ini penulis ingin mengucapkan rasa terima kasih dan penghargaan kepada :
1.
Ayahanda M.O Harahap, S.Sos I, Ibunda Dahlia dan Abang saya Ridwan Fahlevi Harahap atas doa restunya da kasih sayangnya yang tiada habisnya diberikan pada penulis serta dukungan moril dan materil yang tanpa jasanya tak mungkin penulis sampai pada saat sekarang.
2.
Bapak Prof. Drs. Subhilhar, M.A, Ph.Dselaku Rektor Universitas Sumatera Utara.
3.
Bapak Prof. Dr. Muhammad Zarlis, M.Kom selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi.
4.
Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S1 Ilmu Komputer.
5.
Ibu Maya Silvi Lydia, B.Sc, M.Sc selaku Sekretaris Program Studi Ilmu Komputer.
6.
BapakDr. Syahril Efendi, SSi, M.IT.selaku Dosen Pembimbing I dan Ibu Dian Rachmawati, S.Si, M.Komselaku Dosen Pembimbing II yang telah meluangkan waktu, tenaga, dan pikiran dalam membimbing, mengarahkan, menasehati, memotivasi, dan menyemangati penulis agar dapat menyelesaikan skripsi ini.
7.
Bapak Drs. Marihat Situmorang, M.Kom selaku dosen Pembanding I dan Bapak Amer Sharif, S.Si, M.Kom selaku dosen Pembanding II yang telah memberikan kritik dan saran terhadap skripsi penulis.
Universitas Sumatera Utara
v 8.
Seluruh staf pengajar dan pegawai Fakultas Ilmu Komputer dan Teknologi Informasi.
9.
Sahabat-sahabat luar biasa Chasika Rani Purba, Fitria Andhika, Tengku Zikri Rachman, Nugra Atsaury Saragih dan Rudi Setiawan selalu menemani dan memberi motivasi kepada penulis.
10. Teman – teman seperjuangan mahasiswa/i S1 Ekstensi Ilmu Komputer stambuk 2012 yang selalu memberi dukungan. 11. Semua pihak yang terlibat langsung ataupun tidak langsung yang tidak dapat penulis ucapkan satu per satu yang telah membantu menyelesaikan skripsi ini.
Penulis menyadari bahwa skripsi ini masih memiliki banyak kekurangan, baik dari segi teknik, tata penyajian ataupun dari segi tata bahasa. Oleh karena itu penulis bersedia menerima kritik dan saran dari pembaca dalam upaya perbaikan skripsi ini. Semoga skripsi ini dapat bermanfaat bagi penulis dan pembaca, khususnya rekan-rekan mahasiswa lainnya yang mengikuti perkuliahan di Universitas Sumatera Utara.
Medan, Penulis
September 2015
Rini Chairani Harahap
Universitas Sumatera Utara
vi ABSTRAK Bandara internasional Kuala Namu merupakan Bandar udara Internasional yang melayani kota medan dan sekitarnya. Komputer banyak digunakan untuk melakukan pencarian lintasan terpendek (shortest path), yang ditampilkan dalam model simulasi.Ide dari penelitian ini berawal dari masalah jarak tempuh untuk menuju Bandara Kuala Namu.Faktor ketepatan dalam memilih jarak terpendek untuk sampai pada bandara sangat penting untuk mencegah ketinggalan pesawat.Pencarian jarak terpendek ini memfokuskan hanya untuk mencari jalur terdekat menuju Bandara Kuala Namu yang disimbolkan dengan sebuah titik (vertex).Algoritma yang digunakan untuk pencarian jarak terpendek adalah Floyd Warshall.Hasil yang diperoleh dalam pencarian jarak terpendek antar verteks adalah rute-rute yang dilalui.
Kata kunci:Algoritma Floyd Warshall, Shortest Path, Bandara Internasional Kuala Namu.
Universitas Sumatera Utara
vii
Floyd Warshall Algorithme Implementation For DetermineThe Shortest Path (Medan- KNIA) ABSTRACT Kuala Namu International Airport is an international airport serving Medan and surrounding areas. Computers are widely used to search the shortest path, which is shown in the simulation model. The idea of this study originated from mileage problem to get to the Kuala Namu Airport. Accuracy factor in choosing the shortest path to arrive at the airport is very important to prevent miss the plane. The shortest path focused only to find the nearest path towards Kuala Namu Airport that is symbolized by a point(vertex). The algorithm used to search the shortest path is Floyd Warshall. The results obtained in the search for the shortest path between vertex are the passed routes. Keywords:Floyd Warshall algorithm, Shortest Path, Kuala Namu International Airport.
Universitas Sumatera Utara
viii DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv vi vii viii x xi
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan
1 1 2 2 3 4 4 5
Bab 2 Landasan Teori 2.1 Graph 2.1.1 Macam – macam Graph Menurut Arah dan Bobotnya 2.2 Lintasan Terpendek (Shortest Path) 2.3 Algoritma 2.3.1 Pegertian Algoritma 2.3.2 Algoritma Floyd Warshall 2.3.3 Analisis Algoritma Floyd Warshall
7 7 8 11 11 11 13 15
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Persyaratan 3.2 Pemodelan Aplikasi 3.2.1 Use-Case Diagram 3.2.2 Activity Diagram 3.2.3 Sequence Diagram 3.3 Flowchart 3.4 Perancangan Interface 3.5 Database 3.6 Entity Relationship Diagram (ERD)
17 17 17 19 20 20 21 23 24 25 26 28
Bab 4 Implementasi Dan Pengujian Sistem 4.1 Implementasi Sistem 4.1.1 Tampilan Halaman Utama 4.1.2 Tampilan Menu Floyd 4.1.3 Tampilan Login Admin Pengelola Data
29 29 29 30 30
Universitas Sumatera Utara
ix 4.1.4 Tampilan Data Lokasi 4.2 Graph Yang Digunakan Untuk Menentukan Rute Terpendek 4.3 Perhitungan Algoritma Floyd Warshall 4.3.1 Iterasi Pertama 4.3.2 Iterasi Ke Dua 4.3.3 Iterasi Ke Tiga 4.3.4 Iterasi Ke Empat 4.3.5 Iterasi Ke Lima 4.3.6 Iterasi Ke Enam 4.3.7 Iterasi Ke Tujuh 4.3.8 Iterasi Ke Delapan 4.3.9 Iterasi Ke Sembilan 4.3.10 Iterasi Ke Sepuluh 4.3.11 Iterasi Ke Sebelas 4.3.12 Iterasi Ke Dua Belas 4.4 Tampilan Rute 4.4.1 Focal Point – KNIA 4.4.2 Pinang Baris – KNIA 4.4.3 Medan Plaza – KNIA 4.4.4 Sun Plaza – KNIA 4.4.5 Hermes Place – KNIA 4.4.6 Amplas – KNIA 4.4.7 Paladium – KNIA 4.4.8 Centre Point – KNIA 4.4.9 Thamrin Plaza – KNIA 4.4.10 Medan Mall – KNIA Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
31 31 33 33 34 34 35 36 37 38 39 40 41 42 43 44 44 44 45 45 46 46 47 47 48 48
49 50
DAFTAR PUSTAKA LAMPIRAN A [KODE PROGRAM] LAMPIRAN B [DAFTAR RIWAYAT HIDUP]
Universitas Sumatera Utara
x DAFTAR TABEL Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 3.4 Tabel 3.5 Tabel 4.1 Tabel 4.2 Tabel 4.3 Tabel 4.4 Tabel 4.5 Tabel 4.6 Tabel 4.7 Tabel 4.8 Tabel 4.9 Tabel 4.10 Tabel 4.11 Tabel 4.12
Tabel tbljarak Tabel tbljlhpengguna Tabel tblpengunjung Tabel tblmap Tabel tblnode Perhitungan algoritma Floyd Iterasi Pertama Perhitungan Algoritma Floyd Iterasi Ke Dua Perhitungan Algoritma Floyd Iterasi Ke Tiga Perhitungan Algoritma Floyd Iterasi Ke Empat Perhitungan Algoritma Floyd Iterasi Ke Lima Perhitungan Algoritma Floyd Iterasi Ke Enam Perhitungan Algoritma Floyd Iterasi Ke Tujuh Perhitungan Algoritma Floyd Iterasi Ke Delapan Perhitungan Algoritma Floyd Iterasi Ke Sembilan Perhitungan Algoritma Floyd Iterasi Ke Sepuluh Perhitungan Algoritma Floyd Iterasi Ke Sebelas Perhitungan Algoritma Floyd Iterasi Ke Dua Belas
Halaman 26 26 27 27 27 33 34 34 35 36 37 38 39 40 41 42 43
Universitas Sumatera Utara
xi DAFTAR GAMBAR
Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 2.6 Gambar 2.7 Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4 Gambar 3.5 Gambar 3.6 Gambar 3.7 Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8 Gambar 4.9 Gambar 4.10 Gambar 4.11 Gambar 4.12 Gambar 4.13 Gambar 4.14 Gambar 4.15
Halaman Graph dengan 4 Vertex dan 5 Edge 8 Graph Berarah dan Berbobot 8 Graph Tidak Berarah dan Berbobot 9 Graph Berarah dan Tidak Berbobot 9 Graph Tidak Berarah dan Tidak Berbobot 10 Graph Sederhana 10 Graph Tidak Sederhana 10 Ishikawa Diagram 18 Use Case Sistem Penentuan Jalur Terpendek Menuju KNIA 20 Activity Diagram Algoritma Floyd Warshall 22 Sequence Diagram 23 Diagram Alur Algoritma Floyd Warshall 24 Perancangan Interface 25 Entity Relationship Diagram (ERD) 28 Tampilan Halaman Utama 29 Tampilan Menu Floyd 30 Tampilan Login Admin 30 Tampilan Data Lokasi 31 Graph Yang Digunakan Untuk Menghitung Jarak Terpendek 31 Menuju KNIA Tampilan Rute Focal Point – KNIA 44 Tampilan Rute Pinang Baris – KNIA 44 45 Tampilan Rute Medan Plaza – KNIA Tampilan Rute SUN Plaza – KNIA 45 Tampilan Rute Hermes Polonia – KNIA 46 46 Tampilan Rute Amplas – KNIA Tampilan Rute Paladium – KNI 47 Tampilan Rute Centre Point – KNIA 47 Tampilan Rute Thamrin Plaza – KNIA 48 Tampilan Rute Medan Mall – KNIA 48
Universitas Sumatera Utara
