SKRIPSI DEBI SULARMAN HUTABALIAN

SISTEM INFORMASI GEOGRAFIS UNTUK MENENTUKAN RUTE TERPENDEK MENGGUNAKAN ALGORITMA DIJKSTRA BERBASIS WEB (STUDI KASUS PADA SALAH SATU BIMBINGAN BELAJAR DI KOTA MEDAN)

SKRIPSI

DEBI SULARMAN HUTABALIAN 101421041

PROGRAM STUDI S1 EKSTENSI ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer

DEBI SULARMAN HUTABALIAN 101421041

PROGRAM STUDI S1 EKSTENSI ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014


PERSETUJUAN

: SISTEM INFORMASI GEOGRAFIS UNTUK MENENTUKAN RUTE TERPENDEK MENGGUNAKAN ALGORITMA DIJKSTRA BERBASIS WEB (STUDI KASUS PADA SALAH SATU BIMBINGAN BELAJAR DI KOTA MEDAN) : Kategori SKRIPSI : DEBI SULARMAN HUTABALIAN Nama Nomor Induk Mahasiswa : 101421041 Program Studi : S1 EKSTENSI ILMU KOMPUTER Departemen : ILMU KOMPUTER Fakultas : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI (FASILKOM-TI) Judul

Diluluskan di Medan, 11 Februari 2014

Komisi Pembimbing

:

Pembimbing 2

Drs. Marihat Situmorang, M. Kom NIP 19631214 1989031 001

Pembimbing 1

Dr. Poltak Sihombing, M.Kom NIP 19620317 199103 1 001

Diketahui/Disetujui oleh Departemen Ilmu Komputer Fasilkom-TI USU Ketua,

Dr. Poltak Sihombing, M.Kom NIP 19620317 199103 1 001


PERNYATAAN


SKRIPSI

Penulis mengakui bahwa skripsi ini adalah hasil kerja penulis sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, 11 Februari 2014

Debi Sularman Hutabalian 101421041


PENGHARGAAN

Segala puji dan syukur penulis panjatkan kepada Tuhan Yesus Kristus, atas berkat karunia, hikmat dan kebijaksanaan yang diberikan, sehingga penulis dapat menyelesaikan skripsi ini dengan baik. Dengan segala kerendahan hati, pada kesempatan ini penulis menyampaikan terima kasih kepada semua pihak yang telah membantu penyelesaian skripsi ini. Penulis mengucapkan terima kasih kepada: 1. Bapak Prof. Dr. Syahril Pasaribu, DTMH, M.Sc(CTM), SpA(K) sebagai Rektor Universitas Sumatera Utara, 2. Bapak Prof. Muhammad Zarlis, M.Kom sebagai Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, 3.

Bapak Dr. Poltak Sihombing, M. Kom sebagai Ketua Jurusan Ilmu Komputer sekaligus sebagai Pembimbing I,

4. Ibu Maya Silvi Lydia, BSc. MSc sebagai Sekretaris Program Studi S1 Ilmu Komputer, 5. Bapak Drs.Marihat Situmorang, M.Kom selaku Pembimbing II dan sekaligus sebagai Dosen di Program Studi S1 Ilmu Komputer, 6. Bapak Drs. Agus Salim Harahap, M.Si sebagai Dosen Pembanding I dan sekaligus sebagai Dosen di Program Studi S1 Ilmu Komputer, 7. Bapak Ade Candra, S.T,. M.Kom sebagai Dosen Pembanding II dan sekaligus sebagai Dosen di Program Studi S1 Ilmu Komputer, 8. Seluruh Dosen dan Staff Pegawai di Program Studi S-1 Ilmu Komputer Universitas Sumatera Utara, 9. Dan teristimewa untuk kedua orang tua terkasih, Ayahanda Ringkot Hutabalian, S.Pd dan Ibunda Drs. Lindawati Siringo-ringo yang telah memberikan dukungan moril dan materil serta doa yang tidak ternilai kepada penulis sehingga dapat menyelesaikan skripsi ini. 10. Kak Rutdina Rusliani Hutabalian, Kak Togi Marito Hutabalian, A.Md dan Adik Putri Ningsih Astuti Hutabalian, A.Md, serta Bere-bere ku yang lucu, yang selalu memberikan dukungan dan semangat kepada penulis. 11. Terimakasih kepada teman-teman kuliah Program Ekstensi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara yang memberikan masukan, semangat kepada penulis.


12. Kepada Bapak dan Ibu Gembala GPdI Elshaddai, Youth Pastor El’s Generation Pdm. Moody Tambuwun, S.Si dan seluruh teman-teman sepelayanan di GPdI Elshaddai atas doa yang tulus, dorongan, semangat, dan motivasi kepada penulis. 13. Kepada Seluruh teman-teman Komsel 3G, yang sudah banyak memberikan semnagat bahkan doa selama ini. 14. Kepada Dytha_Pianist, makasih nyuk buat motivasinya, doa, dukungan yang tak pernah pudar untuk membakar kobaran api semangat agar dapat memperjuangkan skripsi ini sampai tuntas. 15. Dan tidak lupa kepada seluruh rekan-rekan seperjuangan S1 Ekstensi stambuk 2010 Kom A dan Kom B, serta abang-abang dan kakak-kakak senior yang ada di Program Studi S1 Ilmu Komputer yang telah memberikan dukungan moril kepada penulis dalam penyelesaian skripsi ini. Sekali lagi penulis mengucapkan terima kasih kepada semua pihak yang membantu dalam penyelesaian skripsi ini yang tidak dapat disebutkan satu persatu, terima kasih atas ide, saran, dan motivasi yang diberikan. Penulis menyadari bahwa skripsi ini masih jauh dari kesempurnaan. Oleh karena itu penulis menerima kritik dan saran dari semua pihak yang bersifat membangun dan menyempurnakan skripsi ini. Penulis berharap semoga skripsi ini bermanfaat bagi penulis sendiri pada khususnya dan pembaca pada umumnya.

Terima kasih, Tuhan Yesus Memberkati.

Medan, 11 Februari 2014

Debi Sularman Hutabalian


ABSTRAK

Kota Medan merupakan wilayah Kota yang sedang berkembang dan juga menjadi pusat daerah perdagangan, perindustrian, perkantoran, pariwisata, pendidikan dan lain-lain. Sebagai kota yang sedang berkembang, maka perlu dibangun sebuah layanan informasi mengenai fasilitas umum di Kota Medan Penulis membuat sebuah aplikasi Sistem Informasi Geografis untuk menetukan jarak terpendek suatu Bimbingan Belajar. Google maps digunakan untuk menampilkan peta online dan lintasan terpendek yang akan dilalui, serta jarak yang akan di tempuh. Metode yang digunakan untuk mencari lintasan terpendek ini adalah algoritma Dijkstra. Algoritma Dijkstra adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (direct graph) dengan bobot sisi yang bernilai positif dan terlebih dahulu menentukan node awal dan node tujuan dengan jumlah bobot terkecil.

Kata Kunci: Sistem Informasi Geografis, Pencarian Lintasan Terpendek, Algoritma Dijkstra


Web Based Geographic Information System To Determine Shortest Path Using Dijkstra Algorthm (Case Study One Of Education Center In Medan City)

ABSTRACT

Medan is a developing city and center of commerce, industry, offices, government, tourism, education and etc. As the developing city, so need be b u i l t wit h i nfor ma t i on s e r vic e l i ke publi c fa c i li t y i n t he Meda n Ci t y. After did research, writer make an application of Geographical Information System to determines shortest distance of Education Center. Google maps is used to show online map and shortest path will be traveled and then distance will be taken on. Method is used to search this shorter path is Algorithm of Dijkstra. Algorithm of Dijkstra is a greedy algorithm used to solve shortest path problem for a direct graph with positive weight and before that determined the first node and the purpose node with the sum of small weight.

Keyword : Geographic Information System, Determing a Shortest Path, Dijkstra’s Algoritm


DAFTAR ISI

Halaman Judul Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar

i ii iii iv vi vii viii x xi

Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan

1 1 4 4 5 5 5 6

Bab 2 Landasan Teori 2.1 Pengertian Sistem Informasi Geografis 2.1.1 Data Spasial 2.1.2 Format Data Spasial 2.1.2.1 Model Data Vektor 2.1.2.2 Model Data Raster 2.1.3 Sumber Data Spasial 2.2 Peta 2.2.1 Proyeksi Peta 2.3 Graph 2.4 Pencarian Rute Terpendek Dengan Algoritma Dijkstra 2.5 Geografis Kota Medan

7 7 9 10 10 10 11 12 12 14 16 17

Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Kebutuhan Sistem 3.1.2.1 Kebutuhan Fungsional Sistem 3.1.2.2 Kebutuhan Nonfungsional Sistem 3.1.3 Pemodelan 3.1.3.1 Diagram Konteks 3.1.3.2 Data Flow Diagram (DFD) 3.1.3.2.1 Data Flow Diagram (DFD) Level 0 3.1.3.2.2 Data Flow Diagram (DFD) Level 1

19 19 19 20 20 21 21 22 22 23 23


3.1.3.2.3 Data Flow Diagram (DFD) Level 2 3.1.3.3 Model Data (Entity Relationship Diagram) 3.1.3.4 Desain Database 3.1.3.5 Flowchart 3.1.3.5.1 Flowchart Login Admin 3.1.3.5.2 Flowchart Login Menu Admin 3.1.3.5.3 Flowchart Ubah Pasword 3.1.3.5.4 Flowchart Olah Data Berita 3.1.3.5.5 Flowchart Olah Data Lokasi 3.1.3.5.6 Flowchart Olah Data Admin 3.2 Perancangan Sistem Antar Muka (Interface) 3.2.1 Perancangan Input 3.2.1.1 Perancangan Input Berita 3.2.1.2 Perancangan Ubah Password 3.2.1.3 Perancangan Input Admin 3.2.1.4 Perancangan Input Jarak Terpendek 3.2.2 Perancangan Output 3.2.2.1 Perancangan Olah Data Berita 3.2.2.2 Perancangan Olah Data Lokasi 3.2.2.3 Perancangan Olah Data Admin 3.2.2.4 Perancangan Hasil Pencarian Rute Terpendek 3.3 Perhitungan Rute Terpendek

24 25 25 27 27 28 29 30 31 32 33 33 33 34 35 36 37 37 38 39 40 40

Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi Sistem 4.2 Tampilan Program 4.2.1 Halaman index 4.2.2 Halaman Buku Tamu 4.2.3 Halaman Tentang Algoritma Dijkstra 4.2.4 Halaman About Us 4.2.5 Halaman Pencarian Rute Terpendek 4.3 Pengujian 4.3.1 Pengujian Black Box (Black Box Testing) 4.3.2 Kasus dan hasil pengujian 4.3.2.1 Pengujian login 4.3.2.2 Pengujian pengolahan data admin 4.3.2.3 Pengujian pengolahan data cabang 4.3.2.4 Pengujian pengolahan data cabang 4.3.2.5 Pengujian pengolahan data berita 4.3.2.6 Pengubahan Data Password admin 4.3.2.7 Penginputan data komentar 4.3.2.8 Pencarian rute terpendek

49 49 57 57 57 58 59 59 61 61 62 62 63 65 67 70 72 73 73

Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran

75 75 75

Daftar Pustaka LAMPIRAN A : Listing Program

76 A


DAFTAR TABEL

No. Tabel 3.1 3.2 3.3 3.4 3.5 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17

Nama Tabel Tabel Admin Tabel Lokasi Tabel Berita Tabel Buku Tamu Data Objek Peta Rencana Pengujian Pengujian Login Pengujian Input Data Admin Pengujian Ubah Data Admin Pengujian Hapus Data Admin Pengujian Input Data Cabang Pengujian Ubah Data Cabang Pengujian Hapus Data Cabang Pengujian Input Data Cabang Pengujian Ubah Data Cabang Pengujian Hapus Data Cabang Pengujian Input Data Berita Pengujian Ubah Data Berita Pengujian Hapus Data Berita Pengujian Ubah Data Password Penginputan Data komentar Pencarian rute terpendek

Halaman 25 26 26 26 42 61 62 63 64 65 65 66 67 68 68 69 70 71 71 72 73 73


DAFTAR GAMBAR

No. Gambar 2.1

Nama Gambar

Halaman 8 9 10 11 13

2.6 2.7 2.8 2.9

Ilustrasi Urian Sub-Sistem SIG Model data vector Model Data Raster Perbedaan Proyeksi (a) Cylindrical, (b)Planar dan (c) Conical Contoh Graph Berarah dan Berbobot Contoh Graph tidak berarah dan berbobot Contoh Graph berarah dan tidak berbobot Contoh Graph tidak berarah dan tidak berbobot

3.1

Diagram Ishikawa

20

3.2

Diagram Konteks

22

3.3

Data Flow Diagram (DFD) Level 0

23

3.4


24

3.5


24

3.6

Flowchart Login Admin

27

3.7

Menu Admin

28

3.8

Flowchart Ubah Password

29

3.9

Flowchart Olah Data Berita

30

3.10

Flowchart Olah Data Lokasi

31

3.11

Flowchart Olah Data Admin

32

3.12

User Interface Perancangan Input Berita

33

3.13

User Interface Perancangan Ubah Password

34

3.14

User Interface Perancangan Input Admin

35

3.15

User Interface Perancangan Input Jarak Terpendek

36

3.16

Interface Perancangan Olah Olah Data Berita

37

3.17

User Interface Perancangan Olah Data Lokasi

38

3.18

User Interface Perancangan Olah Data Admin

38

3.19

User Interface Perancangan Hasil Pencarian Jarak

40

2.2 2.3 2.4 2.5

Sub-Sistem SIG

14 15 15 15


Terpendek 3.20

Graph/Titik Objek Bimbinan Belajar

4.1

Contoh Graf Untuk Mencari Rute Terpendek

50

4.2 4.3 4.4

Contoh Algoritma Dijkstra Langkah Pertama Penjelasan Fungsi Label Pada Graf Contoh Algoritma Dijkstra Langkah Kedua

50 50 51

4.5 4.6

Contoh Algoritma Dijkstra Langkah Ketiga Contoh Algoritma Dijkstra Langkah Keempat

52 52

4.7

Contoh Algoritma Dijkstra Langkah Kelima

53

4.8

Contoh Algoritma Dijkstra Langkah Keenam

53

4.9

Contoh Algoritma Dijkstra Langkah Ketujuh

54

4.10

Contoh Algoritma Dijkstra Langkah Kedelapan

54

4.11

Contoh Algoritma Dijkstra Langkah Kesembilan

55

4.12

Contoh Algoritma Dijkstra Langkah Kesepuluh

55

4.13

Contoh Algoritma Dijkstra Langkah Kesebelas

56

4.14

Graf Hasil Pencarian Rute Terpendek Dengan Algoritma

56

Dijkstra 4.15

Tampilan Menu Utama

57

4.16

Tampilan Buku Tamu

58

4.17

Tampilan Tentang Algoritma Dijkstra

58

4.18

Halaman about Us

59

4.19

Halaman Pencarian Rute Terpendek

60

4.20

Tampilan Hasil Pencarian Rute Terpendek

60


SKRIPSI DEBI SULARMAN HUTABALIAN

Recommend Documents