IMPLEMENTASI ALGORITMA BELLMAN FORD DALAM PENCARIAN SEKOLAH TAMAN KANAK-KANAK (TK) TERDEKAT DI KOTA MEDAN BERBASIS SISTEM INFORMASI GEOGRAFIS SKRIPSI

IMPLEMENTASI ALGORITMA BELLMAN – FORD DALAM PENCARIAN SEKOLAH TAMAN KANAK-KANAK (TK) TERDEKAT DI KOTA MEDAN BERBASIS SISTEM INFORMASI GEOGRAFIS

SKRIPSI

SANDRA PUTRI JUNIKA 131401129

PROGRAM STUDI S-1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2017

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer

SANDRA PUTRI JUNIKA 131401129

PROGRAM STUDI S-1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2017


PERSETUJUAN

Judul

: IMPLEMENTASI ALGORITMA BELLMAN-FORD DALAM PENCARIAN SEKOLAH TAMAN KANAK-KANAK (TK) TERDEKAT DI KOTA MEDAN BERBASIS SISTEM INFORMASI GEOGRAFIS Kategori : SKRIPSI Nama : SANDRAPUTRI JUNIKA Nomor Induk Mahasiswa : 131401129 Program Studi : SARJANA(S-1) ILMU KOMPUTER Fakultas : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA

Komisi Pembimbing

:

Pembimbing 2

Sri Melvani Hardi, S.Kom,M.Kom NIP.198805012015042006

Pembimbing 1

M. Andri Budiman, ST,M.Comp.Sc,MEM NIP. 197510082008011011

Diketahui/disetujui oleh Program Studi S1 Ilmu Komputer Ketua,

Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001


PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.

Medan, Juli 2017

Sandra Putri Junika 131401129


PENGHARGAAN

Alhamdulillah. Puji dan syukur kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya, sehingga penulis dapat menyelesaikanpenyusunanskripsi ini sebagai syarat memperolehgelar Sarjana Komputerpada Program Studi S-1 Ilmu Komputer, Fakultas Ilmu Komputer dan Teknologi Informasi Univeristas Sumatera Utara. Dengan segala kerendahan hati, penulis ingin menyampaikanrasa hormatdan terimakasih yang sebesar-besarnya kepada semua pihak yang telah membantu dalam penyelasian skripsi ini. Penulis mengucapkan terimakasih kepada : 1. Bapak Prof. Dr. Runtung Sitepu, S.H., M.Humselaku Rektor Universitas Sumatera Utara. 2. BapakProf. Dr. Opim Salim Sitompul, M.Sc selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi, Universitas Sumatera Utara. 3. Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S-1 Ilmu Komputer Universitas Sumatera Utara. 4. Bapak M. Andri Budiman, ST, M.Comp.Sc, MEM selaku Dosen Pembimbing I yang telah memberikan bimbingan, saran, motivasi dan dukungan kepada penulis dalam pengerjaan skripsi ini. 5. IbuSri Melvani Hardi, S.Kom, M.Kom selaku Dosen Pembimbing II yang telah memberikan bimbingan, saran, motivasi dan dukungan kepada penulis dalam pengerjaan skripsi ini. 6. Ibu Dian Rachmawati, S.Si, M.KomselakuDosen Pembanding I yang memberikankritikdan saran kepada penulis dalam penyempunaanskripsi ini. 7. Bapak Amer Sharif, S.Si, M.Komselaku Dosen Pembanding II yang memberikan kritik dan saran kepada penulis dalam penyempunaan skripsi ini serta selaku Dosen Pembimbing Akademik yang telah memberi arahan selama masa perkuliahan. 8. Seluruh dosen dan staf pegawai Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.


9. Kedua orangtua penulis tercinta ibunda Susi Maisarah Pane dan Ayahanda Ikra Negara Siregar serta adik tercinta Shintia Meidinah yang telah memberikan do’a, dukungan, perhatian, kesabaran, pengorbanan dan kasih sayang yang tak ternilai harganya. 10. Teman-teman semasa kuliah yang selama ini telah menjadi tempat berbagi suka dan duka, yang telah memberikan motivasi, hiburan, dukungan dan nasehat yang tak ternilai kepada penulis, Noer Inda Chayanie, Mutiara Rizky Parlindungan, Tia Rahmadianti, Fadhilah Atika, Jessica,Paulus Arapenta, Raviza Sitepu, Alwi Ahdi Fahrozi, Adiba Nazila Parinduri, Atika Yasinta Lubis, Khairunnisa Nasution dan Putri Chaliska. 11. Teman-teman semasa sekolah yang telah memberikan semangat, dukungan dan saran yang tak ternilai kepada penulis, Fadilla Annisa Harahap, Hasbur Ghali dan Ruth Novita, Amd. 12. Teman-teman kuliah KOM C 2013, serta teman-teman stambuk 2013atas doa dan dukunganya sehingga penulis dapat menyelesaikan skripsi ini. 13. Rekan-rekan pengurus IMILKOM (Ikatan Mahasiswa S1 Ilmu Komputer) Fasilkom-TI USU Periode 2016-2017 yang telah memberikan dukungan, tempat belajar berorganisasi yang benar dan menimba pengalaman. 14. Dan semua pihak yang terlibat secara langsung maupun tidak langsung yang telah banyak membantu yang tidak bisa disebutkan satu-persatu.

Semoga semua kebaikan, bantuan, perhatian, serta dukungan yang telah diberikan kepada penulis mendapatkan berkat yang melimpah dari Allah SWT.

Medan, Juli 2017 Penulis,

Sandra Putri Junika


ABSTRAK

Salah satu kebutuhan mendasar untuk mendapatkan masa depan yang lebih baik adalah pendidikan. Taman Kanak-kanak merupakan pendidikan dasar formal yang pertama kali didapatkan oleh seorang anak. Namun, belum semua orangtua mengetahui letak sekolah TK terdekat yang satu dengan yang lainnya pada ruang lingkup lokasi kerjanya sehingga terjadi ketidakefisenan untuk mengantar anak menuju sekolah TK dan ke tempat kerja. Sehingga dibutuhkannya solusi untuk mencari jarak sekolah terdekat antara lokasi kerja dengan sekolah TK. Terdapat pilihan yang dapat ditempuh orangtua menuju sekolah taman kanak-kanak (TK) yang ada di Kota Medan. Data sekolah TK yang akan ditampilkan adalah sekolah-sekolah yang ruang lingkupnya memiliki jarak terdekat dengan lokasi kerja orangtua yang berprofesi sebagai dosen ataupun staf pegawai yang bekerja di Universitas Sumatera Utara. Jarak maupun rute menuju sekolah TK terdekat diambil dari google maps dengan mengambil jumlah data sekolah sebanyak 10 buah yang nantinya dibuat dalam verteks ke dalam graf yang bersifat statis. Daerah graf yang digunakan dalam penyelesaian pencarian sekolah terdekat menggunakan peta yang diolah berbasis sistem informasi geografis lalu diperoleh hasilnya dalam file .jpg. Hasil pencarian sekolah TK menggunakan algoritma shortest path, yakni Algoritma Bellman-Ford dengan menampilkan nilai jarak, rute dan real running time. Kata kunci: Algoritma Bellman-Ford,Graf,Shortest Path, Taman Kanak-kanak.


IMPLEMENTATION OF BELLMAN-FORD ALGORTIHM INA SEARCH OF THE NEAREST KINDERGARTEN IN MEDAN CITY BASED ON GEOGRAPHIC INFORMATION SYSTEM

ABSTRACT

One of the fundamental needs to get a better future is education. Kindergarten is the first formal basic education obtained by a child. However, not all parents know the location of the nearest kindergarten school with one another in area of work location so that there is inefficiency to take the child to kindergarten school and to workplace. So, it need a solution to find the closest school distance between work location and kindergarten school. There is an option that can be taken by parents to a kindergarten school in the city of Medan. The kindergarten school data that will be display are the schools the area has the closest distance to the work location who work as a lecturer or staff of employees who work at the Universitas Sumatera Utara. The distance and the route to the nearest kindergarten school is taken from google maps by taking the number of school data as many as 10 datas that will be made in the vertex in a static graph. The area of graph used in the nearest school search completion using map based information system and then obtained the result in file .jpg. Kindergarten school search the results. The result of kindergarten search use the shortest path of some kindergartens in Medan using the Bellman-Ford Algorithm by displaying real distance, routes and real running time. Keywords : Bellman-Ford Algorithm, Graph, Shortest Path, Kindergarten.


DAFTAR ISI

Halaman

Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Daftar Lampiran

Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Ruang Lingkup Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan

ii iii iv vi vii viii x xi xii

1 2 2 3 3 4 5

Bab 2 Landasan Teori 2.1 Pengertian Algoritma 2.1.1 Sifat Algoritma 2.2 Teori Dasar Graf 2.2.1 Jenis Graf 2.2.2 Graf Berbobot 2.3 Shortest Path (Jalur Terpendek) 2.4 Algoritma Bellman-Ford 2.5 Sistem Informasi Geografis 2.5.1 Komponen SIG 2.6 Sekolah Taman Kanak-kanak 2.7 Penelitian yang Terdahulu

7 7 8 8 9 10 10 15 16 17 18

Bab 3Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Kebutuhan a. Kebutuhan Fungsional b. Kebutuhan Nonfungsional 3.1.3 Analisis Proses 3.1.4 Flowchart

19 19 25 25 25 26 26


a. Flowchart Sistem b. Flowchart Algoritma 3.2 Perancangan Sistem a. Use case Diagram b. Activity Diagram c. Sequence Diagram 3.3 Perancangan Interface a. Menu Home b. Menu Panduan c. Menu Cari Jalur

27 28 29 29 30 31 32 32 33 34

Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi 36 4.1.1 Tampilan Halaman MenuHome 4.1.2 Tampilan Halaman Menu Cari Jalur 4.1.3 Tampilan Halaman Menu Panduan 4.2 Pengujian 4.2.1 Pengujian Proses Implementasi Algoritma Bellman-Ford 4.2.2 Perhitungan Manual Algoritma Bellman-Ford 4.2.2 Real Running Time 4.3 Kompleksitas Algoritma

36 37 38 38 38 40 41 42

Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2. Saran

44 45

Daftar Pustaka Lampiran

46


DAFTAR TABEL

Halaman Tabel 2.1Hasil Langkah 1 Tabel 2.2Hasil Langkah 2 Tabel 2.3Hasil Langkah 3 Tabel 3.1Daftar Nama Sekolah yang Menjadi Verteks Tabel 3.2Data Setiap Verteks Sekolah TK di Kota Medan Tabel 4.1Langkah 1 Algoritma Bellman-Ford Tabel 4.2 Langkah 2 Algoritma Bellman-Ford Tabel 4.3Langkah 3 Algoritma Bellman-Ford Tabel 4.4Hasil Real Running Time Tabel 4.5 Kompleksitas Algoritma Bellman-Ford

12 13 15 21 24 40 40 41 41 42


DAFTAR GAMBAR

Halaman Gambar 2.1 (a) Graf Sederhana, (b) Graf Ganda, dan (c) Graf Semu Gambar 2.2 (a) Graf Berarah, (b) Graf Ganda Berarah Gambar 2.3 Graf Berbobot Gambar 2.4 Contoh Rute Pencarian Gambar 2.5 Langkah 1 Gambar 2.6 Langkah 2 Gambar 2.7Rute pendek dengan Bellman Ford Gambar 2.8Peta Spasial Digital Gambar 3.1Diagram Ishikawa Gambar 3.2Rute Sekolah Taman Kanak-kanak (TK) di Kota Medan Gambar 3.3Flowchart Sistem Gambar 3.4Flowchart Algoritma Bellman-Ford Gambar 3.5Use Case Diagram Gambar 3.6Activity Diagram Gambar 3.7 Sequence Diagram Gambar 3.8Perancangan Interface Menu Home Gambar 3.9Perancangan Interface Menu Panduan Gambar 4.1 Tampilan Halaman Menu Home Gambar 4.2 Tampilan Halaman Menu Cari Jalur Gambar 4.3 Tampilan Halaman Menu Panduan Gambar 4.4 Tampilan Graf Hasil Pencarian Jalur Terpendek Gambar 4.5 Graf Bellman-Ford

9 9 10 11 11 13 16 19 22 23 24 25 26 27 28 29 30 35 36 37 37 38


DAFTAR LAMPIRAN

Halaman Lampiran 1 Listing Program Lampiran 2Curriculum Vitae

A-1 B-1


IMPLEMENTASI ALGORITMA BELLMAN FORD DALAM PENCARIAN SEKOLAH TAMAN KANAK-KANAK (TK) TERDEKAT DI KOTA MEDAN BERBASIS SISTEM INFORMASI GEOGRAFIS SKRIPSI

Recommend Documents