1 SISTEM INFORMASI GEOGRAFIS BERBASIS WEB SEBAGAI PENENTU SHORTEST PATH DENGAN MENGGUNAKAN ALGORITMA DIJKSTRA SKRIPSI ICHSAN KURNIAWAN DEPARTEMEN S-1 ...
SISTEM INFORMASI GEOGRAFIS BERBASIS WEB SEBAGAI PENENTU SHORTEST PATH DENGAN MENGGUNAKAN ALGORITMA DIJKSTRA
SKRIPSI
ICHSAN KURNIAWAN 041401027
DEPARTEMEN S-1 ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: SISTEM INFORMASI GEOGRAFIS BERBASIS WEB SEBAGAI PENENTU SHORTEST PATH DENGAN MENGGUNAKAN ALGORITMA DIJKSTRA : SKRIPSI : ICHSAN KURNIAWAN : 041401027 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 9 Maret 2010
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
M. Andri Budiman, ST, M.Comp.Sc, MEM NIP 197510082008011011
Drs. James Piter Marbun, M.Kom NIP 195806111986031002
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Prof. Dr. Muhammad Zarlis NIP 195707011986011003
Universitas Sumatera Utara
PERNYATAAN
SISTEM INFORMASI GEOGRAFIS BERBASIS WEB SEBAGAI PENENTU SHORTEST PATH DENGAN MENGGUNAKAN ALGORITMA DIJKSTRA SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 9 Maret 2010
Ichsan Kurniawan 041401027
Universitas Sumatera Utara
PENGHARGAAN
Alhamdulillah, puji syukur penulis panjatkan kehadirat Allah SWT, yang telah memberikan rahmat dan ridho-Nya, sehingga saya dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi Ilmu Komputer Universitas Sumatera Utara. Shalawat dan Salam saya hadiahkan kepada Nabi Besar Muhammad SAW. Ucapan terima kasih yang sebesar-besarnya penulis sampaikan kepada Bapak Drs. James Piter Marbun, M.Kom sebagai Dosen Pembimbing I dan Bapak M. Andri Budiman, ST, M.Comp.Sc, MEM sebagai Dosen Pembimbing II atas bimbingan, saran, masukan kepada penulis untuk menyempurnakan skripsi ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Program Studi Ilmu Komputer, Bapak Prof. Dr. Muhammad Zarlis dan Bapak Syariol Sitorus, S.Si., MIT, Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen, pegawai/staf di Program Studi Ilmu Komputer S-1 USU. Seluruh proses pengerjaan skripsi ini tidak akan dapat dilalui tanpa dukungan orangtua dan seluruh keluarga saya. Terima kasih sebesar-besarnya atas segala dukungannya baik materil dan spiritual. Semoga Allah SWT akan membalasnya. Terima kasih juga kepada tika melayu, seluruh sahabat-sahabat RCS yang sangat saya hormati, serta seluruh teman-teman yang tidak dapat saya sebutkan semuanya. Terima kasih pula kepada semua pihak-pihak yang tidak dapat saya sebutkan satu persatu, terima kasih atas ide, saran, dan kerjasama yang baik. Saya menyadari bahwa skripsi ini masih jauh dari kesempurnaan, karena kesempurnaan hanya milik Allah dan kekurangan adalah milik saya. Oleh karena itu saya menerima saran dan kritik yang bersifat membangun demi kesempurnaan skripsi ini. Semoga skripsi ini dapat bermanfaat bagi kita semuanya.
Universitas Sumatera Utara
ABSTRAK
Transportasi saat ini merupakan kebutuhan yang esensial dalam kehidupan manusia. Seiring dengan perkembangan suatu komunitas maka transportasi akan memiliki berbagai masalah yang terikat dengan jarak dan waktu. Di satu sisi pandang, permasalahan ini sangat erat kaitannya dengan rute (atau jalur) yang dipilih. Kajian ini bertujuan membangun sebuah sistem penentu jalur terpendek pada suatu daerah, dengan input berupa sebuah titik awal dan sebuah titik tujuan. Sistem ini diterapkan pada sebuah Sistem Informasi Geografis dengan menggunakan Algoritma Dijkstra untuk menentukan jalur terpendek. Daerah kajian dalam sistem ini adalah Kota Medan yang citranya telah diproses menjadi sebuah peta digital.
Universitas Sumatera Utara
WEB BASED GEOGRAPHIC INFORMATION SYSTEM TO DETERMINE A SHORTEST PATH USING DIJKSTRA ALGORITHM ABSTRACT
Nowadays, transportation is essential to human life. Along withvthe community growth, there has been various problems associated with transportation in terms of distance and time. In one view, these problems are closely related with the chosen route or path. This study is purposed to build a system to determine the shortest path in a certain area, given an origin node and a destination node. The system is applied to a Geographic Information System and it uses Dijkstra's Algorithm to determine the shortest path. The area employed in the system is the Medan City whose image has been processed into a digital map.
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Gambar Daftar Tabel
ii iii iv v vi vii ix x
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Tujuan Penelitian 1.3 Rumusan Masalah 1.4 Batasan Masalah 1.5 Metode Penelitian 1.6 Sistematika Penulisan
1 1 2 2 3 3 4
Bab 2 Landasan Teori 2.1 Graf 2.1.1 Ketetanggaan 2.1.2 Lintasan 2.1.3 Graf Berbobot 2.1.4 Representasi Graf 2.1.5 Matriks Ketetanggaan (Adjacency Matrix) 2.1.6 Matriks Bersisian (Incidency Matrix) 2.1.7 Senarai Ketetanggaan (Adjacency List) 2.2 Lintasan Terpendek (Shortest Path) 2.3 Algoritma Dijkstra 2.4 Sistem Informasi Geografis 2.4.1 Komponen Sistem Informasi Geografis 2.5 Matriks Asal-Tujuan (Origin Des tination Matrix) 2.6 Mapserver 2.7 Ka-Map 2.8 XML (eXtensible Markup Language) 2.9 Pengujian Perangkat Lunak 2.9.1 Pengujian Cacat 2.9.1.1 Pengujian Kotak Hitam 2.9.1.2 Pengujian Struktural 2.9.1.3 Pengujian Jalur 2.9.2 Pengujian Integrasi
Bab 3 Analisis dan Desain Sistem 3.1 Analisis Masalah Umum 3.2 Deskripsi Sistem 3.3 Spesifikasi Keperluan Sistem 3.3.1 Fungsi Sistem 3.3.2 Tujuan Sistem 3.3.3 Masukan dan Keluaran Sistem 3.3.4 Batasan Sistem 3.4 Data Flow Diagram (DFD) 3.5 Desain Database 3.6 Perancangan Antarmuka Sistem (Interface)
27 27 33 33 34 34 34 34 35 39 40
Bab 4 Implementasi dan Pengujian Sistem 4.1 Implementasi 4.1.1 Lingkungan Implementasi 4.2 Pengujian Sistem 4.2.1 Pengujian Shortest Path antara Node Terkecil dan Node Terbesar 4.2.2 Pengujian dengan Shortest Path dengan Jalur Satu Arah 4.2.3 Pengujian Kesesuaian Pemilihan Jalur Shortest Path dengan Nilai Total Jalur yang Ditempuh 4.3 Tampilan Aplikasi Sistem . Bab 5 Kesimpulan Dan Saran 5.1 Kesimpulan 5.2 Saran
42 42 43 44
Daftar Pustaka Lampiran
53 55
44 44 45 46 51 51 51
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 2.1 Graf Tak Berarah Gambar 2.2 Graf Berarah Gambar 2.3 Graf Ketetanggaan Gambar 2.4 Graf Berbobot Gambar 2.5 Graf Matriks Ketetanggaan Gambar 2.6 Graf Matriks Bersisian Gambar 2.7 Representasi Jalur Beberapa Kota Gambar 2.8 Arsitektur Dasar Aplikasi MapServer Gambar 2.9 Aplikasi DetikMap Gambar 2.10 Aplikasi Minnesota DNR Gambar 2.11 Aplikasi Visualitation of Resource Map Gambar 2.12 Pengujian Kotak Hitam Gambar 3.1 Flowchart Algoritma Dijkstra Gambar 3.2 Graf Analisis Dijkstra Gambar 3.3 Diagram Konteks Gambar 3.4 DFD Level 1 Gambar 3.5 DFD Level 2 Gambar 3.6 Flowchart Sistem Gambar 3.7 Rancangan Antarmuka Sistem Gambar 4.1 Tampilan Awal Aplikasi Gambar 4.2 Tampilan Zoom In 1 x Gambar 4.3 Pemilihan Node Awal Gambar 4.4 Pemilihan Node Akhir Gambar 4.5 Tampilan Query Gambar 4.6 Tampilan Jalur Hasil Query
Tahap 1 Analisis Dijsktra Tahap 2 Analisis Dijkstra Tahap 3 Analisis Dijkstra Tahap 4 Analisis Dijkstra Tahap 5 Analisis Dijkstra Entitas Data Pada DFD Level 1
30 31 31 32 32 36
Universitas Sumatera Utara
BAB I
PENDAHULUAN
1.1 Latar Belakang Masalah
Transportasi adalah persoalan penting bagi masyarakat kota yang dinamis. Banyaknya jalan terkadang menyulitkan seseorang untuk mencapai tempat tujuannya. Terbatasnya waktu yang dimiliki dan pengaruh ekonomi mempengaruhi masyarakat untuk mencapai tempat tujuannya secepat mungkin dengan lintasan terpendek (shortest path). Untuk membantu dalam menentukan lintasan terpendek dapat menggunakan peta konvensional dan memilih jalur yang terpendek dari tempat asal ke tujuan. Namun hal ini sering kali tidak dapat membantu secara maksimal karena banyaknya jalan yang harus dipilih dan tidak dapat diperkirakan jarak tempuh pada jalur itu.
Untuk itu diperlukan suatu sistem yang dapat membantu dalam menentukan lintasan terpendek yang dapat merepresentasikan data yang ada. Data tersebut dapat disimpan, diolah, dan disajikan dalam bentuk yang lebih sederhana serta terkomputerisasi sehingga memudahkan dalam penentuan lintasan terpendek.
Dalam tugas akhir ini akan digunakan sistem informasi geografis yang berfungsi sebagai peta digital yang dapat merepresentasikan daerah tertentu. Dan disini digunakan juga algoritma Dijkstra sebagai penentu lintasan terpendek dimana persimpangan dan fasilitas umum dari sistem informasi geografis tersebut yang menjadi vertex.
Universitas Sumatera Utara
Aplikasi ini akan dibuat berbasis web karena aplikasi berbasis web dianggap lebih memiliki beberapa keunggulan dibandingkan aplikasi berbasis desktop, diantaranya adalah sebagai berikut: 1. Tidak mengharuskan hardware atau software tertentu. Aplikasi web based dapat dijalankan selama komputer memiliki browser. 2. Instalasi relatif lebih mudah, karena hanya melakukan instalasi pada server saja. 3. Lebih murah, karena banyak aplikasi berbasis web yang open source. 4. Pengembangan lebih mudah. Aplikasi berbasis web menggunakan script, sehingga tidak perlu melakukan compile. Hanya melakukan perubahan script pada server maka client akan mengikuti perubahan.
1.2 Tujuan Penelitian
Tujuan dari penulisan tugas akhir ini adalah untuk membangun suatu prototipe sistem informasi geografis dengan mengimplementasikan algoritma Dijkstra sehingga dapat menentukan lintasan terpendek.
1.3 Rumusan Masalah
Bagaimana mengimplementasikan algoritma Dijkstra ke dalam sebuah sistem informasi geografis sehingga dapat digunakan untuk mencari lintasan terpendek pada suatu rute.
1.4 Batasan Masalah
Batasan masalah pada tugas akhir ini adalah sebagai berikut: 1. Perhitungan dalam pencarian lintasan terpendek menggunakan satu kendaraan dengan jenis dan tipe yang sama, dan kecepatan laju kendaraan yang sama dan konstan.
Universitas Sumatera Utara
2. Jalanan yang dilalui tidak mengalami kerusakan ataupun gangguan lainnya. 3. Konflik
pergerakan
seperti
merging,
crossing,
dan
diverging
pada
persimpangan dianggap tidak ada. 4. Kendaraan lain yang melintasi pada jalur pencarian dianggap tidak pernah menghalangi. 5. Lampu lalu lintas dianggap tidak ada. 6. Jarak lintasan dianggap merupakan jarak pergerakan kendaraan dari centroid tempat asal ke centroid tempat tujuan. 7. Jalan yang menjadi edge pada graf hanya jalan protokol. 8. Menggunakan algoritma Dijkstra untuk mencari lintasan terpendek. 9. Kendaraan yang digunakan tidak melalui rute khusus yang telah ditentukan. 10. Tidak membahas mengenai pembuatan dan pengolahan data spasial. 11. Vertex berupa fasilitas umum berupa bank, instansi pemerintahan, rumah sakit, hotel, tempat ibadah, pusat perbelanjaan, terminal transportasi, dan lainnya yang dilalui jalan protokol ataupun persimpangan jalan protokol.
1.5 Metode Penelitian
Langkah-langkah yang akan diambil dalam pengerjaan tugas akhir ini adalah sebagai berikut:
1. Studi Literatur. Pengerjaan tugas akhir ini dimulai dengan mengumpulkan bahan-bahan sebagai referensi baik dari buku, paper, jurnal, makalah, forum, milis, dan sumber-sumber lain yang berkaitan dan beberapa referensi lainnya untuk menunjang pencapaian tujuan tugas akhir. 2. Observasi. Metode ini dilakukan dengan melakukan pengamatan dan pengujian terhadap beberapa sistem informasi geografis dan aplikasi untuk mencari lintasan terpendek dengan melakukan penelusuran di internet. Dengan pengamatan secara langsung tersebut akan diperoleh pengetahuan bagaimana bentuk sistem yang ada dan telah diimplementasikan. 3. Analisis. Pada tahap ini dilakukan analisis permasalahan yang ada, batasan yang dimiliki dan kebutuhan yang diperlukan.
Universitas Sumatera Utara
4. Perancangan dan Implementasi Algoritma. Metode ini akan dilaksanakan dengan
melakukan
perancangan
sistem
informasi
geografis
dan
mengimplementasikan algoritma Dijkstra dalam membangun sistem ini. 5. Pengujian. Pada tahap ini dilakukan pengujian terhadap sistem informasi geografis yang telah dibangun serta menguji kebenaran dari algoritma Dijkstra untuk mencari lintasan terpendek. 6. Penyusunan
Laporan
dan
Kesimpulan
Akhir.
Metode
ini
akan
dilaksanakan dengan melakukan pendokumentasian hasil analisis dan implementasi secara tertulis dalam bentuk laporan skripsi.
1.6 Sistematika Penulisan
Sistematika penulisan dari skripsi ini terdiri dari beberapa bagian utama sebagai berikut:
BAB 1: PENDAHULUAN Bab ini akan menjelaskan mengenai latar belakang pemilihan judul skripsi “Sistem Informasi Geografis Berbasis Web sebagai Penentu Shortest Path dengan Menggunakan Algoritma Dijkstra”, rumusan masalah, batasan masalah, tujuan penelitian, manfaat penelitian, metode penelitian, dan sistematika penulisan.
BAB 2: LANDASAN TEORI Bab ini akan membahas teori-teori yang berkaitan dengan sistem, graf, algoritma Dijkstra, dan sistem informasi geografis.
BAB 3: ANALISIS DAN DESAIN SISTEM Bab ini berisikan langkah-langkah penelitian yang dilakukan, serta analisis terhadap fokus permasalahan penelitian.
BAB 4: IMPLEMENTASI DAN PENGUJIAN SISTEM Bab ini berisikan hasil desain sistem serta pembahasan terhadap desain tersebut.
Universitas Sumatera Utara
BAB 5: KESIMPULAN DAN SARAN Bab terakhir akan memuat kesimpulan isi dari keseluruhan uraian bab-bab sebelumnya dan saran-saran dari hasil yang diperoleh yang diharapkan dapat bermanfaat dalam pengembangan selanjutnya.
Universitas Sumatera Utara
BAB II
LANDASAN TEORI
2.1 Graf
Menurut Rinaldi Munir (2003), “Graf adalah struktur diskrit yang terdiri dari simpul (vertex) dan sisi (edge), atau dengan kata lain, graf adalah pasangan himpunan (V, E) dimana V adalah himpunan tidak kosong dari vertex dan E adalah himpunan sisi yang menghubungkan sepasang simpul dalam graf tersebut”.
Berdasarkan orientasi arah pada sisi, secara umum graf dibedakan atas dua jenis, yaitu sebagai berikut: 1. Graf tak berarah. Graf tak berarah adalah graf yang sisinya tidak mempunyai orientasi arah. Pada graf tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (vj, vk) = (vk, vj) adalah sisi yang sama.
Gambar 2.1 Graf tak berarah
2. Graf berarah. Graf berarah adalah graf yang sisinya diberikan orientasi arah. Pada umumnya, sisi yang berarah disebut dengan busur (arc). Pada graf berarah, (vj, vk) dan (vk, vj) menyatakan 2 buah busur yang berbeda, atau dengan kata lain (vj, vk) ≠
Universitas Sumatera Utara
(vk, vj). Untuk busur (vj, vk), simpul vj dinamakan simpul asal (initial vertex) dan simpul vk dinamakan simpul terminal (terminal vertex).
Gambar 2.2 Graf berarah
Pada tugas akhir ini, yang digunakan adalah graf berarah, karena graf berarah dapat merepresentasikan jalan yang ada. Dimana tidak semua jalan memiliki dua arah yang saling berlawanan, namun ada juga jalan yang hanya memiliki satu arah saja.
2.1.1 Ketetanggaan
Dua buah vertex pada graf tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, vj bertetangga dengan vk jika (vj, vk) adalah sebuah sisi pada graf G.
Gambar 2.3 Graf Ketetanggaan
Pada gambar 2.3, simpul 1 bertetanggaan dengan simpul 2 dan 3, tetapi simpul 1 tidak bertetanggaan dengan simpul 4.
Universitas Sumatera Utara
2.1.2 Lintasan
Rinaldi Munir (2003, hal: 306) mengatakan, “Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpulsimpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2, … , vn-1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), … , en = (vn-1, vn) adalah sisi – sisi dari graf G”. Jika graf yang ditinjau merupakan graf sederhana, maka lintasan cukup dituliskan sebagai barisan simpul: v0, v1, v2, …, vn-1, vn, karena antara dua buah simpul yang berurutan dalam lintasan tersebut hanya terdapat satu sisi.
Jika graf yang ditinjau memiliki sisi ganda, maka, lintasan ditulis sebagai barisan berselang-seling antara simpul dan sisi: v0, e1, v1, e2, v2, e3, …, vn-1, en, vn. Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan yang semua simpulnya berbeda (setiap sisinya dilalui hanya sekali) dikatakan lintasan sederhana.
2.1.3 Graf Berbobot
Graf berbobot adalah graf yang setiap sisinya diberikan sebuah harga (bobot). Bobot pada setiap sisi dapat menyatakan jarak antara dua buah kota, biaya perjalanan, waktu tempuh, ongkos produksi, dan sebagainya.
Gambar 2.4 Graf Berbobot
Universitas Sumatera Utara
2.1.4 Representasi Graf
Menurut Rinaldi Munir (2003), “Agar graf dapat diproses dalam program komputer, graf harus direpresentasikan ke dalam memori. Terdapat beberapa representasi untuk graf, antara lain matriks ketetanggaan, matriks bersisian dan senarai ketetanggaan”.
2.1.5 Matriks Ketetanggaan (Adjacency Matrix)
Misalkan G = (V, E) graf sederhana dimana |V| = n, n > 1. Maka, matriks ketetanggaan A dari G adalah matriks n x n dimana A = [aij], [aij] menjadi 1 bila simpul i dan j bertetangga [aij] menjadi 0 bila simpul i dan j tidak bertetangga Jumlah elemen matriks bertetanggaan untuk graf dengan n simpul adalah n2. Jika tiap elemen membutuhkan ruang memori sebesar p, maka ruang memori yang diperlukan seluruhnya adalah pn2.
Keuntungan representasi dengan matriks ketetanggaan adalah kita dapat mengakses elemen matriksnya langsung dari indeks. Selain itu, kita juga dapat menentukan dengan langsung apakah simpul i dan simpul j bertetangga.
Pada graf berbobot, aij menyatakan bobot tiap sisi yang menghubungkan simpul i dengan simpul j. Bila tidak ada sisi dari simpul i ke simpul j atau dari simpul j ke simpul i, maka, aij diberi nilai tak berhingga.
Gambar 2.5 Graf Matriks Ketetanggaan
Universitas Sumatera Utara
Bentuk matriks ketetanggaan dari graf pada gambar 2.5 adalah
1
2
3
4
1
0
0
1
0
2
0
0
1
1
3
1
1
0
1
4
0
1
1
0
2.1.6 Matriks Bersisian (Incidency Matrix)
Matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalkan G = (V, E) adalah graf dengan n simpul dan m sisi, maka matriks kebersisian A dari G adalah matriks berukuran m x n dimana
A = [aij], [aij] menjadi 1 bila simpul i dan sisi j bersisian [aij] menjadi 0 bila simpul i dan sisi j tidak bersisian
Gambar 2.6 Graf Matriks Bersisian
Bentuk matriks bersisian dari graf pada gambar 2.6 adalah
e1
e2
e3 e4
1
0
0
0
1
2
1
1
0
0
3
0
1
1
1
4
1
0
1
0
Universitas Sumatera Utara
2.1.7 Senarai Ketetanggaan (Adjacency List)
Matriks ketetanggaan memiliki kelemahan apabila graf memiliki jumlah sisi yang relatif sedikit sehingga graf sebagian besar berisi bilangan 0. Hal ini merupakan pemborosan terhadap memori, karena banyak menyimpan bilangan 0 yang seharusnya tidak perlu disimpan. Untuk kepentingan efisiensi ruang, maka tiap baris matriks tersebut digantikan senarai yang hanya berisikan vertex-vertex dalam adjacency set Vx dari setiap vertex x.
Bentuk senarai ketetanggan berdasarkan graf pada gambar 2.5 adalah 1: 3 2: 3,4 3: 1,2,4 4: 2,3
2.2 Lintasan Terpendek (Shortest Path)
Lintasan terpendek merupakan lintasan paling minimum yang ditempuh dari suatu tempat untuk mencapai tempat tujuan tertentu. Graf yang digunakan merupakan graf berbobot, yaitu graf yang setiap edge-nya memiliki nilai. Nilai pada sisi graf dapat berupa jarak, waktu, biaya, ataupun yang lainnya.
Ada beberapa macam persoalan lintasan terpendek, antara lain adalah sebagai berikut: 1. Lintasan terpendek antara dua buah simpul tertentu. 2. Lintasan terpendek antara semua pasangan simpul. 3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain. 4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
Dalam pencarian lintasan terpendek ada beberapa algoritma yang dapat dipergunakan namun, disini yang digunakan adalah algoritma Dijkstra dalam menentukan lintasan terpendek.
Universitas Sumatera Utara
2.3 Algoritma Dijsktra
Algoritma Dijkstra merupakan algoritma untuk menentukan jarak terpendek dari satu vertex ke vertex yang lainnya pada suatu graf berbobot, dimana jarak antar vertex adalah nilai bobot dari setiap edge pada graf tersebut. Dan bobot harus bernilai posisif (bobot >= 0). Algoritma Dijkstra ditemukan oleh Edger Wybe Dijkstra. Algoritma Dijkstra mencari jarak terpendek dari vertex asal ke vertex terdekatnya, kemudian ke vertex yang kedua, dan seterusnya. Dalam setiap iterasinya, algoritma akan menambahkan vertex lain ke lintasan terpendek spanning tree.
Algoritma ini menggunakan strategi greedy dalam menentukan lintasan terpendek. Dalam strategi greedy pada setiap langkahnya akan memilih sisi yang berbobot minimum dan memasukkannya ke dalam himpunan solusi. Diharapkan pada setiap langkah dapat memilih solusi optimum lokal sehingga mencapai solusi optimum global.
2.4 Sistem Informasi Geografis
Menurut Purwadhi (1994), “Sistem Informasi Geografis merupakan suatu sistem yang mengorganisasi perangkat keras (hardware), perangkat lunak (software), dan data, serta dapat mendayagunakan sistem penyimpanan, pengolahan maupun analisis data secara simultan, sehingga dapat diperoleh informasi yang berkaitan dengan aspek keruangan”.
Sedangkan menurut Cowen (1998), “Sistem Informasi Geografis juga dapat dikatakan sebagai sistem pendukung keputusan (decision support system) yang computerized, yang melibatkan integrasi data spasial dalam memecahkan masalah lingkungan”
Sistem Informasi Geografis merupakan suatu sistem yang menarik, sistem yang cenderung dibuat interaktif ini dapat mengintegrasikan data spasial (peta vektor dan citra digital), atribut (tabel sistem database), audio, video dan lain sebagainya.
Universitas Sumatera Utara
Hasil integrasi tersebut membuat Sistem Informasi Geografis memiliki berbagai fungsionalitas, antara lain adalah sebagai berikut: 1. Kemampuan
dasarnya
sebagai
mapping
system
dengan
kemampuan
kartografisnya. 2. Melakukan query terhadap data spasial ataupun data atribut yang terkait. 3. Menampilkan dan mengolah data permukaan tiga dimensi sebagai alat Bantu pemodelan dengan aspek dimensi ketiga.
2.4.1 Komponen Sistem Informasi Geografis
Sistem Informasi Geografis merupakan hasil dari beberapa komponen. Menurut Robinson et al (1995), komponen Sistem Informasi Geografis terbagi menjadi empat, yaitu sebagai berikut: 1. Perangkat Keras (Hardware) Sistem Informasi Geografis membutuhkan komputer untuk menyimpan data dan dalam melakukan pengolahan data. Semakin kompleks data yang ingin diolah, maka semakin besar juga kebutuhan memori dan kecepatan pengolah datanya. 2. Perangkat Lunak (Software) Perangkat
lunak
dibutuhkan
untuk
memasukkan,
menyimpan
dan
mengeluarkan data bila diperlukan. Perangkat lunak Sistem Informasi Geografis harus memiliki beberapa elemen seperti mampu melakukan input dan transformasi data geografis, sistem manajemen basis data, mampu mendukung query geografis, analisis dan visualisasi, dan memiliki Graphical User Interface (GUI) untuk memudahkan akses. 3. Data Dalam SIG semua data dasar geografis harus diubah terlebih dahulu ke dalam bentuk digital untuk memudahkan dalam pengolahan data. Data dalam SIG dibagi menjadi dua bentuk yakni geografical atau data spasial, dan data atribut. a. Menurut Perpres No.85 (2007), “Data spasial adalah data hasil pengukuran, pencatatan dan pencitraan terhadap suatu unsur keruangan
Universitas Sumatera Utara
yang berada di bawah, pada atau di atas permukaan bumi dengan posisi keberadaannya mengacu pada sistem koordinat nasional”. b. Menurut Denny Charter (2008), “Data atribut adalah gambaran data yang terdiri dari informasi yang relevan terhadap suatu lokasi seperti kedalaman, ketinggian, lokasi penjualan, dan lain-lain dan bisa dihubungkan dengan lokasi tertentu dengan maksud untuk memberikan identifikasi seperti alamat, kode pos, dan lain-lain”. 4. Manusia Manusia dibutuhkan untuk mengendalikan seluruh Sistem Informasi Geografis. Adanya koordinasi dalam Sistem Informasi Geografis sangat diperlukan agar informasi yang diperoleh menjadi benar, tepat dan akurat.
Sistem Informasi Geografis merupakan manajemen data spasial dan nonspasial yang berbasis komputer dengan tiga karakteristik dasar, yaitu sebagai berikut: 1. Mempunyai fenomena aktual (variabel data non-lokasi) yang berhubungan dengan topik permasalahan di lokasi yang bersangkutan. 2. Merupakan suatu kejadian di suatu lokasi. 3. Mempunyai dimensi waktu.
Dalam Sistem Informasi Geografis, ada dua jenis model peta yang digunakan, yaitu sebagai berikut: 1. Peta vektor Peta vektor merupakan peta yang dibangun dari penggabungan berbagai titik acuan yang kemudian melalui perhitungan khusus, titik-titik tersebut akan saling dihubungkan membentuk suatu garis atau pola tertentu. 2. Peta raster Peta raster adalah peta dalam bentuk citra gambar yang merupakan hasil fotografi dari satelit ataupun hasil scan dari peta konvensional.
Dalam tugas akhir ini yang digunakan adalah peta vektor. Karena peta dalam bentuk vektor tidak terpengaruh oleh resolusi, karena itu apabila peta dibesarkan atau dkecilkan akan tidak mengalami pixelate. Di sisi lain, peta dalam bentuk vektor juga
Universitas Sumatera Utara
menghasilkan file dalam ukuran yang lebih kecil dari raster, sehingga dapat lebih menghemat memori.
Transportasi yang baik sangatlah menunjang dalam perkembangan suatu daerah. Pada tingkatan tertentu, transportasi dapat mengalami masalah-masalah. Untuk mengatasi masalah tersebut adalah dengan memahami pola pergerakan orang atau barang yang ada. Salah satu metode untuk memahami pola tersebut adalah dengan menggunakan matriks asal-tujuan (Origin Destination Matrix).
Matriks asal-tujuan dapat digunakan untuk membentuk tabel jarak antar vertex yang akan memudahkan dalam merepresentasikan graf.
Gambar 2.7 Representasi jalur beberapa kota
Misalkan terdapat sebuah graf yang merepresentasikan jalur dari beberapa kota seperti gambar 2.7, maka bentuk dari matriks asal-tujuannya adalah:
A
B
C
D
E
Ti
A
0
0
150
0
80
270
B
0
0
50
120
0
170
C
150
50
0
0
100
300
D
0
120
0
0
30
150
E
80
0
100
30
0
210
Tj
270
170
300
150
210 2100
Universitas Sumatera Utara
2.6 MapServer
MapServer merupakan proyek open source yang dikenal yang ditujukan untuk menampilkan peta spasial dinamis melalui internet. Beberapa keistimewaan utama dari MapServer adalah sebagai berikut: 1. Mendukung untuk menampilkan dan melakukan query peta raster, vektor, dan format database. 2. Mampu berjalan pada berbagai jenis sistem operasi (windows, linux, Mac OS X, dan lainnya). 3. Mendukung bahasa scripting yang umum (PHP, Python, Perl, Ruby, Java, .NET). 4. Render kualitas tinggi. 5. Output aplikasi yang dapat diubah sesuai keinginan.
Pada dasarnya, MapServer adalah program CGI (Common Gateway Interface) yang tidak aktif pada web server. Ketika suatu request dikirim ke MapServer, MapServer menggunakan informasi yang dikirimkan dalam URL yang diminta dan Mapfile untuk membuat gambar dari peta yang diminta. Request dapat menghasilkan gambar untuk legenda, skala, peta referensi sesuai variabel CGI.
Aplikasi MapServer pada dasarnya mencakup beberapa bagian, yaitu: 1. Mapfile Mapfile adalah sebuah file konfigurasi berbentuk tulisan yang terstruktur untuk aplikasi MapServer. Mapfile menentukan letak peta, dimana dan kemana harus menampilkannya. Mapfile juga menentukan lapisan peta, termasuk sumber data, proyeksi dan simbol. File ini harus berekstensi .map agar MapServer mengenali file ini. 2. Data Geografis MapServer dapat menggunakan banyak jenis data geografis. Format dasar MapServer adalah ESRI shapefile.
Universitas Sumatera Utara
3. Halaman HTML Halaman HTML merupakan antarmuka antara user dan MapServer. Ini merupakan bentuk paling sederhana, MapServer dapat digunakan untuk menempatkan gambar peta statis pada halaman HTML. 4. MapServer CGI Binary atau file yang dapat dieksekusi yang menerima requests dan mengembalikan gambar, data, dan lainnya. MapServer CGI berada pada direktori cgi-bin atau direktori scripts pada server HTTP. 5. Server HTTP Menyajikan halaman HTML kepada user. Dibutuhkan server HTTP yang berfungsi, seperti Apache atau Microsoft IIS (Internet Information Server) untuk menjalankan MapServer.
Arsitektur dasar dari aplikasi MapServer dapat dilihat pada gambar 2.8 berikut ini:
Gambar 2.8 Arsitektur Dasar Aplikasi MapServer
Universitas Sumatera Utara
2.7 ka-Map
ka-Map adalah API Javascript untuk mengembangkan aplikasi web-mapping dengan interface yang sangat interaktif menggunakan fitur-fitur yang tersedia pada browser modern. ka-Map merupakan proyek berbasis open source.
ka-Map dapat digunakan untuk berbagai macam aplikasi. ka-Map memiliki banyak fitur yang menarik, antara lain sebagai berikut: 1. Interaktif, navigasi yang kontinu, tanpa harus reload halaman. 2. Navigasi melalui keyboard. 3. Mendukung skala, legenda dan peta referensi. 4. Pengaturan tampilan layer pada client. 5. Melakukan query dasar.
ka-Map didesain dengan menggunakan sistem caching sesering mungkin. Sistem caching ini akan menyimpan peta ke dalam file pada komputer user, sehingga saat user ingin menuju pada tampilan yang telah di-load sebelumnya sistem tidak akan me-load ulang, sistem akan mengambil file yang telah disimpan sebelumnya untuk ditampilkan. Hal ini dapat menghemat waktu load peta.
Pada ka-Map, setiap peta dibagi menjadi beberapa bagian kecil sehingga membentuk gambar persegi. Gambar-gambar itu kemudian disimpan ke dalam file cache. Setiap kali peta ditampilkan dengan ka-Map pada skala tertentu, ka-Map mengatur area tertentu dan mengambil potongan gambar yang merepresentasikannya. Bila potongan gambar ini telah ada pada file cache, maka ka-Map tidak lagi mengakses data melalui MapServer.
ka-Map sangat baik untuk aplikasi web-mapping dengan data peta statis, skala yang tetap, peta yang sangat besar dan peta yang diubah ukurannya secara dinamis. Sebaliknya ka-Map tidak baik untuk data peta yang sangat dinamis.
Beberapa contoh penggunaan aplikasi web-mapping dengan menggunakan kaMap antara lain adalah sebagai berikut:
Universitas Sumatera Utara
1. Detikmap (http://map.detik.com) Aplikasi web-mapping beberapa kota di Pulau Jawa dengan fasilitas legenda, pencarian dan tempat lokasi kejadian berita pada situs detik.com
Gambar 2.9 Aplikasi DetikMap
2. Minnesota Department of Natural Resources (http://www.dnr.state.mn.us/ volunteer/julaug06/wildriver.html) Aplikasi web-mapping pada daerah St. Croix Valley. Pada aplikasi ini dapat dilihat kontur daerah peta secara 3 dimensi.
Universitas Sumatera Utara
Gambar 2.10 Aplikasi Minnesota DNR
3. Visualitation of resource maps of Cheruvannur Gramma Panchayat (http://cheruvannur.web4all.in/resources/) Aplikasi web-mapping dengan legenda hasil bumi. Pada aplikasi ini terdapat fitur untuk menampilkan atau meniadakan suatu layer pada peta.
Gambar 2.11 Aplikasi Visualitation of Resource Maps
Universitas Sumatera Utara
2.8 XML (eXtensible Markup Language)
XML (eXtensible Markup Language) adalah sekumpulan aturan-aturan yang mendefinisikan
suatu
sintaks
yang
digunakan
untuk
menjelaskan,
dan
mendeskripsikan teks atau data dalam sebuah dokumen melalui penggunaan tag. XML merupakan sebuah bahasa markup yang digunakan untuk mengolah metadata (informasi tentang data) yang menggambarkan struktur dan maksud/ tujuan data yang terdapat dalam dokumen XML, namun bukan menggambarkan format tampilan data tersebut. XML juga dapat digunakan untuk mendefinisikan domain tertentu lainnya, seperti musik, matematika, keuangan dan lain-lain yang menggunakan bahasa markup terstruktur.
XML terletak pada inti web service, yang digunakan untuk mendeskripsikan data. Fungsi utama dari XML adalah komunikasi antar aplikasi, integrasi data, dan komunikasi aplikasi eksternal dengan partner luaran. Dengan standarisasi XML, aplikasi-aplikasi yang berbeda dapat dengan mudah berkomunikasi antar satu dengan yang lain.
XML merupakan sebuah format yang dapat digunakan untuk pertukaran data (interchange) antar aplikasi dan platform yang berbeda. Metode deskripsi data XML (self-describing) membuatnya menjadi pilihan efektif untuk solusi antar jaringan, ebusiness, dan aplikasi terdistribusi. XML juga bersifat dapat diperluas (extensible), dapat digunakan pada semua bahasa pemrograman, dan datanya dapat ditransfer dengan mudah melalui protokol standar internet seperti HTTP tanpa dibatasi oleh firewall.
Sebuah dokumen XML terdiri dari bagian bagian yang disebut dengan node. Node-node itu adalah sebagai berikut: a. Root node yaitu node yang melingkupi keseluruhan dokumen. Dalam satu dokumen XML hanya ada satu root node. Node-node yang lainnya berada di dalam root node.
Universitas Sumatera Utara
b. Element node yaitu bagian dari dokumen XML yang ditandai dengan tag pembuka dan tag penutup, atau bisa juga sebuah tag tunggal elemen kosong seperti . Root node biasa juga disebut root element. c. Attribute note termasuk nama dan nilai atribut ditulis pada tag awal sebuah elemen atau pada tag tunggal. d. Text node, adalah teks yang merupakan isi dari sebuah elemen, ditulis diantara tag pembuka dan tag penutup. e. Comment node adalah baris yang tidak dieksekusi oleh parser. f. Processing Instruction node, adalah perintah pengolahan dalam dokumen XML. Node ini ditandai awali dengan karakter . Namun perlu diingat bahwa header standard XML bukanlah processing instruction node. Header standard bukanlah bagian dari hirarki pohon dokumen XML. 7. NameSpace Node, node ini mewakili deklarasi namespace.
2.9 Pengujian Perangkat Lunak
Menurut Pressman, pengujian sistem adalah sederetan pengujian yang berbeda yang tujuan utamanya adalah sepenuhnya mempergunakan sistem berbasis komputer. Sedangkan menurut Kruse, uji coba atau testing adalah proses menjalankan suatu program dengan data yang telah dipilih untuk mencari kesalahan jika memang ada.
2.9.1 Pengujian Cacat
Tujuan pengujian cacat (defect testing) adalah mengungkap cacat laten pada sistem perangkat lunak sebelum sistem diserahkan kepada user. Hal ini berlawanan dengan pengujian validasi yang ditujukan untuk mendemonstrasikan bahwa sistem telah memenuhi spesifikasinya. Pengujian validasi menuntut sistem berlaku dengan benar dengan menggunakan kasus uji penerimaan. Uji cacat yang berhasil merupakan uji yang menyebabkan sistem berlaku tidak benar dan dengan demikian mengungkap
Universitas Sumatera Utara
adanya cacat. Hal ini menekankan fakta penting mengenai pengujian. Pengujian menunjukkan keberadaan, bukan tidak adanya ataupun kesalahan program.
2.9.1.1 Pengujian Kotak Hitam
Pengujian fungsional atau pengujian kotak hitam (black-box testing) merupakan pendekatan pengujian yang ujinya diturunkan dari spesifikasi program atau komponen. Sistem merupakan kotak hitam yang perilakunya hanya dapat ditentukan dengan mempelajari input dan output yang berkaitan. Nama lain untuk cara ini adalah pengujian fungsional karena penguji hanya berkepentingan dengan fungsionalitas dan bukan implementasi perangkat lunak.
Gambar 2.12 Pengujian Kotak Hitam
Gambar 2.12 mengilustrasikan model sistem yang diasumsikan pada pengujian kotak hitam. Pendekatan ini dapat juga diterapkan pada sistem yang disusun sebagai fungsi atau objek. Jika output bukan merupakan yang diramalkan berarti uji tersebut telah berhasil mendeteksi masalah dengan perangkat lunak tersebut.
Universitas Sumatera Utara
2.9.1.2 Pengujian Struktural
Menurut Summerville (2003, hal: 91), ”Pengujian struktural merupakan pendekatan terhadap pengujian yang diturunkan dari pengetahuan struktur dan implementasi perangkat lunak. Pendekatan ini kadang-kadang disebut pengujian ‘kotak putih (whitebox
testing)’,
pengujian
kotak
kaca
atau
pengujian
kotak
jernih
untuk
membedakannya dari pengujian kotak hitam”.
Pengujian struktural biasanya diterapkan untuk unit program yang relatif kecil. Sebagaimana ditunjukkan oleh namanya, penguji dapat menganalisis kode dan menggunakan pengetahuan mengenai struktur komponen untuk menurunkan data uji. Analisis kode dapat digunakan untuk menemukan berapa kasus uji yang dibutuhkan untuk menjamin bahwa semua statement pada program paling tidak diuji satu kali pada proses pengujian.
2.9.1.3 Pengujian Jalur
Menurut Summerville (2003, hal: 93), “Pengujian jalur (path testing) adalah strategi pengujian struktural yang bertujuan untuk melatih setiap jalur eksekusi independent melalui komponen atau program. Jika setiap jalur independen dieksekusi, maka semua statement pada komponen harus dieksekusi paling tidak satu kali. Lebih jauh lagi, semua statement kondisional diuji untuk kasus true dan false”.
2.9.2 Pengujian Integrasi
Begitu komponen telah teruji, dilanjutkan dengan integrasi untuk membentuk sistem parsial atau lengkap. Pengujian integrasi harus dikembangkan dari spesifikasi sitem. Pengujian integrasi memiliki beberapa strategi pengujian, diantaranya adalah pengujian top-down, pengujian bottom-up, pengujian interface dan pengujian stress.
Universitas Sumatera Utara
Presman mengatakan validasi dapat ditentukan dengan berbagai cara, tetapi definisi yang sederhana adalah “bahwa validasi berhasil bila perangkat lunak berfungsi dengan cara yang dapat diharapkan secara bertanggung jawab oleh pelanggan. Validasi perangkat lunak dicapai melalui sederatan pengujian Black-Box yang memperlihatkan komformitas dengan persyaratan”.
Universitas Sumatera Utara
BAB III
ANALISIS DAN DESAIN SISTEM
3.1 Analisis Masalah Umum
Shortest path merupakan suatu persoalan untuk mencari lintasan antara dua buah vertex pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada edge graf yang dilalui dengan jumlah yang paling minimum atau dapat dinyatakan juga sebagai berikut :
Diberikan sebuah graf berbobot (dengan himpunan vertex V, himpunan edge E, dan fungsi bobot bernilai bilangan real yang dapat ditulis dengan f : E→ R ), dan diberikan elamen v’ dari V , sehingga dapat dicari sebuah lintasan P dari v ke setiap v dari V, sehingga:
∑ f ( P) p∈P
adalah nilai minimal dari semua lintasan yang menghubungkan v ke v’.
Algoritma Dijkstra merupakan salah satu algoritma yang umum digunakan untuk menyelesaikan masalah pencarian jalur terpendek. Secara umum langkahlangkah algoritma Dijkstra dapat dituliskan sebagai berikut: 1. Buat daftar jarak, daftar vertex sebelumnya, daftar vertex yang telah dikunjungi dan daftar vertex saat ini. 2. Semua nilai pada daftar jarak diberi nilai tidak terhingga kecuali vertex awal yang diberi nilai 0. 3. Semua nilai pada vertex yang telah dikunjungi di-set menjadi false.
Universitas Sumatera Utara
4. Semua nilai pada vertex sebelumnya diberikan nilai khusus yang menyatakan belum terdefinisi, seperti null. 5. Vertex saat ini di-set menjadi vertex awal. 6. Tandai vertex menjadi telah dikunjungi. 7. Perbarui daftar jarak dan daftar vertex sebelumnya berdasarkan vertex mana yang dapat segera dikunjungi dari vertex saat ini. 8. Perbarui vertex saat ini ke semua vertex yang belum dikunjungi yang dapat dicapai oleh shortest path dari vertex awal. 9. Ulangi dari langkah 6 sampai semua titik dikunjungi.
Sedangkan flowchart algoritma Dijkstra dapat digambarkan ke dalam gambar 3.1 berikut:
START
Universitas Sumatera Utara
A
Apakah nilai awal state lebih besar dari nilai state yang baru
B
Tidak
Ya
Perbarui nilai state dengan nilai yang baru
Nilai state tetap
Bandingkan nilai state antar kolom vertex yang belum fixed
Berikan status fixed dan posisi saat ini pada state dengan nilai yang terkecil
Apakah nilai terkecil serta status fixed dan posisi saat ini tepat berada pada vertex yang dituju
Tidak
Ya
Output Hasil
END
Gambar 3.1 Flowchart Algoritma Dijkstra
Universitas Sumatera Utara
Misalkan dimiliki sebuah contoh graf dengan 5 vertex dan 7 edge sebagai berikut:
Gambar 3.2 Graf Analisis Dijkstra
Dalam contoh graf, dicari shortest path dari vertex A ke vertex C. Berikut analisis dari shortest path dari vertex A ke vertex C. Tahap 1: 1. Inisialisasi nilai seluruh vertex dengan nilai ‘0’ dan nilai ‘1’ untuk vertex yang telah dikunjungi. 2. Seluruh nilai edge yang terhubung dengan vertex A dimasukkan ke dalam bobot. Dimana nilai edge A ke B = 3 dan A ke E = 4, untuk vertex C,D, dan E tidak diberi nilai karena tidak terhubung dengan vertex A. 3. Predecessor dari A, B dan E adalah A, karena jarak dihitung dari A, sedangkan untuk C, D dan E tidak ada karena tidak ada edge yang terhubung dengan vertex A. Hasil tahap 1 dapat dilihat pada tabel 3.1 di bawah ini.
Tabel 3.1 Tahap 1 Analisis Dijkstra
Keterangan\Vertex Status Bobot Predecessor
A 1 A
B 0 3 A
C 0 -
D 0 -
E 0 4 A
Tahap 2: 1. Berdasarkan kondisi tabel 3.1, dipilih vertex yang memiliki bobot yang paling kecil dengan status ‘0’. Dengan ketentuan itu didapat vertex B. Untuk itu
Universitas Sumatera Utara
vertex B dikunjungi dan status vertex B diubah menjadi 1. Dan predecessor tetap A. 2. Karena vertex B telah dipilih, maka terjadi perubahan pada vertex C, dimana perubahan tersebut adalah bobot vertex C bernilai 7, dan predecessor dari C menjadi B. Karena vertex C didapat dengan melalui vertex B. Hasil dari tahap 2 dapat dilihat pada tabel 3.2.
Tabel 3.2 Tahap 2 Analisis Dijkstra
Keterangan\Vertex Status Bobot Predecessor
A 1 A
B 1 3 A
C 0 7 B
D 0 -
E 0 4 A
Tahap 3: 1. Berdasarkan hasil proses tahap 2, didapatkan vertex dengan state ‘0’ dan bobot terkecil adalah vertex E. Untuk itu status vertex E diberi nilai ‘1’ 2. Karena vertex E telah dipilih, maka terjadi bobot pada vertex D berubah menjadi 5, dan predecessor vertex D menjadi E. Hasil dapat dilihat pada tabel 3.3 di bawah ini.
Tabel 3.3 Tahap 3 Analisis Dijsktra
Keterangan\Vertex Status Bobot Predecessor
A 1 A
B 1 3 A
C 0 7 B
D 0 5 E
E 1 4 A
Tahap 4: 1. Dari hasil proses tahap 3, maka vertex selanjutnya yang dikunjungi adalah vertex D, karena vertex D yang memiliki state ‘0’ dan memiliki bobot terkecil. Untuk itu status vertex D diberi nilai ‘1’ 2. Karena vertex D dipilih, maka nilai bobot pada vertex C berubah menjadi 6, dan predecessor vertex C menjadi D. Hasil ditunjukkan pada tabel 3.4 di bawah.
Universitas Sumatera Utara
Tabel 3.4 Tahap 4 Analisis Dijkstra
Keterangan\Vertex Status Bobot Predecessor
A 1 A
B 1 3 A
C 0 6 B
D 1 5 E
E 1 4 A
Tahap 5: 1. Karena hanya tinggal vertex C yang belum dikunjungi, maka status vertex C diberi nilai ‘1’. Dengan demikian seluruh vertex telah dikunjungi, dan berikut tabel hasil akhir analisis:
Tabel 3.5 Tahap 5 Analisis Dijkstra
Keterangan\Vertex Status Bobot Predecessor
A 1 A
B 1 3 A
C 1 6 B
D 1 5 E
E 1 4 A
Dengan demikian didapatkan jarak terpendek dari vertex A ke seluruh vertex yang ada. Dan jalur yang akan dilalui dapat dilihat berdasarkan predecessor-nya. Berikut adalah shortest path dari vertex A ke vertex lainnya: 1. A ke B, vertex yang dilalui adalah A-B, total jarak 3. 2. A ke C, vertex yang dilalui adalah A-E-D-C, total jarak 6. 3. A ke D, vertex yang dilalui adalah A-E-D, total jarak 5. 4. A ke E, vertex yang dilalui adalah A-E, total jarak 4.
3.2 Deskripsi Sistem
Tugas Akhir ini akan membangun sebuah prototype sistem yang menunjukkan jarak terpendek antara dua node, yang diimplementasikan kepada suatu sistem informasi geografis. Sistem ini dapat digunakan oleh siapa saja yang membutuhkan petunjuk terhadap jalan di Kotamadya Medan.
Universitas Sumatera Utara
Pada sistem ini akan diberikan beberapa node-node tertentu dari peta Kotamadya Medan, yang umumnya berupa persimpangan dari jalan-jalan utama yang ada di Kotamadya Medan. User kemudian memilih data awal dan data akhir yang diinginkan, kemudian sistem akan melakukan perhitungan dan menentukan jalur terpendek yang harus dilalui di antara kedua node tersebut.
Dalam sistem informasi geografis dengan shortest path ini menggunakan file berformat XML sebagai database sistem untuk menyimpan data vertex dan bobot edge serta menyimpan data query hasil perhitungan shortest path.
3.3 Spesifikasi Keperluan Sistem
Dalam skripsi ini, dibangun sebuah sistem pencari jalur terpendek yang mengimplementasikan algoritma Dijkstra. Sistem ini dirancang menggunakan metode pendekatan atas-bawah (Top-Down Approach) sehingga perancangan dimulai dari bentuk yang paling umum, kemudian diturunkan secara bertahap menjadi bentuk yang lebih detail. Spesifikasi umum kebutuhan sistem menjelaskan dasar pembuatan rancangan sistem yang terdiri dari fungsi sistem, tujuan sistem, masukan dan keluaran sistem, dan batasan sistem.
3.3.1 Fungsi Sistem
Sistem yang akan dibuat memiliki fungsionalitas berikut: 1. Menampilkan peta Kotamadya Medan 2. Menunjukkan node-node yang merupakan beberapa persimpangan dan landmark di Kotamadya Medan 3. Menghitung jarak terpendek antara semua node 4. Menampilkan jalur terpendek pada peta
Universitas Sumatera Utara
3.3.2 Tujuan Sistem
Sistem yang akan dibuat memiliki tujuan untuk menghitung dan menunjukkan jarak terpendek dari node awal ke node tujuan pada peta.
3.3.3 Masukan dan Keluaran Sistem
Masukan (input) sistem berupa data awal dan data akhir yang dipilih dari node-node yang telah ditentukan saat inisialisasi peta, sedangkan keluaran (output) sistem adalah jalur-jalur yang dilalui shortest path dari data awal ke data akhir pada peta.
3.3.4 Batasan Sistem
Sistem yang akan dibuat memiliki batasan-batasan berikut: 1. Node yang dapat dipilih sebagai data awal dan data akhir tertentu. 2. Peta yang ditampilkan hanya peta Kotamadya Medan.
3.4 Data Flow Diagram (DFD)
Untuk membantu perancangan sistem digunakan DFD (Data Flow Diagram), yaitu suatu model logika data atau proses yang dibuat untuk menggambarkan dari mana asal data dan kemana tujuan data yang keluar dari sistem, dimana data disimpan, proses apa yang menghasilkan data tersebut dan interaksi antara data yang tersimpan dan proses yang dikenakan pada data tersebut. Model fungsional ini berfungsi membantu memahami cara kerja sistem dan hubungan setiap proses dalam sistem secara terstruktur dan logis.
Pada perancangan Perangkat Lunak Sistem Informasi Geografis dengan Shortest Path, Context diagram dapat dilihat pada Gambar 3.3. Sedangkan DFD rinci yang menggambarkan sistem sebagai jaringan kerja antara fungsi yang berhubungan
Universitas Sumatera Utara
satu sama lain dengan aliran dan penyimpanan data, model ini hanya memodelkan sistem dari sudut pandang fungsi.
DFD dari Sistem Informasi Geografis dengan Shortest Path dapat dilihat pada gambar 3.4 dan gambar 3.5.
SISTEM INFORMASI
Gambar 3.3 Diagram Konteks
Diagram konteks berfungsi menggambarkan hubungan antara entitas luar, berupa masukan dan keluaran sistem. Dari gambar 3.3 dapat dilihat bahwa hanya terdapat sebuah entitas luar, yaitu user. User disini bertindak sebagai source terminal yang memberikan masukan ke sistem dan juga sebagai sink terminal yang menerima keluaran dari sistem itu sendiri.
Berdasarkan diagram konteks pada gambar 3.3, DFD level 1 hanya memiliki satu proses yaitu proses untuk menentukan shortest path, maka DFD level 1 dapat digambarkan sebagai berikut:
Data Asal, Data Tujuan, Jarak
Data Asal 1.1 TENTUKAN SHORTEST PATH
USER
Data Tujuan
Jalur Shortest Path
DATABASE NODE DAN JARAK
DATABASE JALUR SHORTEST PATH
Jalur Shortest Path
Gambar 3.4 DFD Level 1
Pada proses Tentukan Shortest Path membutuhkan data masukan berupa data asal dan data akhir, dan kemudian proses akan mengambil data dari database node dan jarak. Lalu sistem akan melakukan pemeriksaan pada database jalur shortest path,
Universitas Sumatera Utara
bila data awal dan data akhir yang dipilih sudah pernah diproses sebelumnya, maka akan diambil hasil proses dari database jalur shortest path, apabila belum pernah, maka sistem akan memproses data tersebut, selanjutnya sistem akan menyimpan hasil perhitungan dan query jalur shortest path pada database jalur shortest path.
Masing-masing entitas data yang tercantum pada DFD level 1 ditampilkan pada tabel di bawah ini.
Tabel 3.6 Entitas Data Pada DFD Level 1
Nama Data Asal Data Tujuan Jalur Shortest Path
Keterangan Node yang dipilih sebagai vertex asal shortest path Node yang dipilih sebagai vertex akhir shortest path Hasil perhitungan shortest path
Proses tentukan shortest path terdiri dari tiga proses, yaitu proses baca data, proses hitung shortest path dan proses query jalur shortest path. DFD level 2 untuk proses tentukan shortest path dapat digambarkan sebagai berikut:
1
Gambar 3.5 DFD Level 2
Proses baca data (1.1.1) berfungsi membaca data dari database. Proses ini membaca data vertex dan edge dari database node dan jarak dan membaca data jalur
Universitas Sumatera Utara
shortest path hasil proses hitung shortest path (1.1.2) sebelumnya yang telah disimpan ke dalam database jalur shortest path.
Bila data jalur shortest path yang dicari belum tersimpan, maka proses baca data akan melanjutkan ke proses hitung shortest path. Kemudian proses ini akan menyimpan hasil perhitungan ke dalam database jalur shortest path dan melanjutkan kepada proses query jalur shortest path (1.1.3) yang selanjutnya akan ditampilkan pada peta. Secara umum alur proses sistem dapat dilihat pada flowchart sebagai berikut:
START
Gambar 3.6 Flowchart Sistem
Universitas Sumatera Utara
Secara garis besar, algoritma Sistem Informasi Geografis dengan Shortest Path ini dapat dituliskan sebagai berikut: 1. Mulai. 2. Inisialisasi peta. 3. Membaca data seluruh node dan bobot edge pada database node dan jarak. 4. Input node awal dan node tujuan. 5. Memeriksa pada database jalur shortest path apakah query jalur dengan node awal dan node tujuan dari input langkah 3 telah tersimpan. Bila telah ada lanjut ke langkah 7. 6.
Melakukan proses algoritma Dijkstra dengan input node dari langkah 3, simpan hasil proses pada database jalur shortest path.
7. Melakukan query data pada peta. 8. Menampilkan jalur terpendek pada peta. 9. Selesai.
3.5 Desain Database
Pada sistem ini tidak menggunakan aplikasi database seperti SQL, tetapi sistem ini menggunakan format file XML sebagai pengganti database sistem. File XML digunakan pada sistem ini karena data pada sistem tidak dinamis, dan file XML mudah untuk diakses dan dimanipulasi.
Pada sistem ini digunakan dua buah file XML, yaitu file SP.xml dan file path .xml. File SP.xml terdiri dari data node, koordinat node, label node, informasi node yang terhubung, dan jarak antar node. Sedangkan file path.xml yang merupakan data jalur untuk query hasil perhitungan shortest path. Berikut format penulisan pada file SP.xml:
1 2 3 4
1
Universitas Sumatera Utara
5
6
<x>457.68
7
389.075
8
<e>
9
2.3886590
10
4.6055284
11 12
13
Berikut penjelasan dari format penulisan file SP.xml: 1. Baris 1 menjelaskan pada file ini XML mengacu pada versi 1.0 dan menggunakan standar encoding karakter set ISO-8859-1 (Latin-1/West European). 2. Baris 2 merupakan tag pembuka dari element root. Disini menjelaskan bahwa file ini merupakan file yang berhubungan dengan graf. 3. Baris 3 merupakan tag pembuka dari element child. Baris ini menjelaskan bahwa data graf memiliki elemen v yang dimaksudkan sebagai vertex. 4. Baris 4 sampai baris 8 menjelaskan bahwa elemen v memiliki sub elemen sebagai berikut: a. Id vertex dengan nilai 1. b. Label vertex dengan nilai Simpang Selayang. c. Koordinat x dari vertex 1 dengan nilai 457.68. d. Koordinat y dari vertex 1 dengan nilai 389.075. e. Tag pembuka sub elemen e sebagai edge yang memiliki sub sub elemen. 5. Baris 9 menjelaskan sub dari sub elemen e, yaitu con untuk menunjukkan vertex yang terhubung dengan vertex 1, dan memiliki atribut id bernilai 2. con ini memiliki nilai 2.3886590 yang dimaksudkan sebagai jarak antara vertex 1 dan vertex 2.
Universitas Sumatera Utara
3.6 Perancangan Antarmuka Sistem (Interface)
Rancangan antarmuka dari sistem ini hanya terdiri dari satu bagian, hasil query perhitungan shortest path juga akan ditampilkan pada bagian ini juga. Halaman akan di-reload dengan menunjukkan hasil dari query perhitungan shortest path.
Antarmuka sistem ini terdiri dari empat bagian, yaitu button zoom in/ zoom out untuk melakukan pembesaran dan pengecilan pada tampilan peta, button cari shortest path untuk mencari jalur shortest path dari node awal dan node akhir yang telah dipilih, button reset untuk mengulangi pemilihan node, bila terjadi kesalahan dalam pemilihan dan tampilan peta yang memiliki node sebagai pilihan untuk node awal atau node akhir. Berikut adalah rancangan antarmuka sistem:
Gambar 3.7 Rancangan Antarmuka Sistem
Universitas Sumatera Utara
BAB IV
IMPLEMENTASI DAN PENGUJIAN SISTEM
4.1 Implementasi
Aplikasi ini dibangun berbasiskan web dan dapat digunakan pada jaringan internet. Namun pada penelitian ini, implementasi sistem tidak dilakukan sampai tahap implementasi pada jaringan internet secara nyata. Implementasi sistem ini hanya untuk untuk mengetahui kerja sistem dan analisis algoritma Dijkstra pada sistem informasi geografis.
Perangkat lunak yang digunakan dalam mendesain sistem ini adalah ka-Map 1.0. Dimana penggunaan ka-Map ini adalah sebagai framework untuk memudahkan dalam membangun sistem.
Aplikasi ini bertujuan untuk menunjukkan jalur terpendek pada sistem informasi geografis yang berupa peta Kotamadya Medan hasil citra dari foto pesawat tahun 2005. Sistem ini hanya menunjukkan jalur terpendek dari beberapa jalan protokol pada Kotamadya Medan.
Aplikasi pada Tugas Akhir akan diimplementasikan dengan berbasis web. Aplikasi berbasis web dianggap lebih memiliki beberapa keunggulan dibandingkan aplikasi berbasis desktop, seperti tidak mengharuskan hardware atau software tertentu, selama komputer memiliki browser aplikasi dapat dijalankan. Instalasi relatif lebih mudah, karena hanya melakukan instalasi pada server saja. Lebih murah, karena banyak aplikasi berbasis web yang open source. Pengembangan lebih mudah. Aplikasi berbasis web menggunakan script, sehingga tidak perlu melakukan compile. Hanya melakukan perubahan script pada server maka client akan mengikuti perubahan.
Universitas Sumatera Utara
Pada aplikasi ini menggunakan file XML sebagai pengganti database. File XML digunakan karena data pada aplikasi ini statis, dan file XML dianggap mudah untuk diakses dan dimanipulasi, file XML juga dapat digunakan dengan bahasa pemrograman apapun.
4.1.1 Lingkungan Implementasi
Lingkungan implementasi yang akan dijelaskan merupakan lingkungan perangkat keras (hardware) dan perangkat lunak (software) yang digunakan dalam penulisan skripsi ini.
Spesifikasi perangkat keras yang digunakan adalah sebagai berikut: 1.
Processor Intel(R) Pentium 4 3.0 GHz.
2.
Memory RAM 512 MB.
3.
Harddisk Seagate 160 GB.
4.
Perangkat output berupa monitor CRT 14”.
5.
Perangkat input berupa mouse dan keyboard.
Spesifikasi perangkat lunak yang digunakan adalah sebagai berikut: 1.
Operating system Microsoft Windows XP SP2.
2.
Mozilla Firefox version 3.3.5.
3.
Mapserver 4 Windows (MS4W) version 2.2.7.
4.
HTML, CSS, Javascript, XML.
4.2 Pengujian Sistem
Pengujian sistem ini dilakukan untuk melihat apakah algoritma Dijkstra dapat menentukan shortest path pada sistem. Pengujian ini dilakukan dengan dua test case. 1.
Pengujian shortest path antara node terkecil dan node terbesar.
2.
Pengujian dengan shortest path dengan jalur satu arah.
Universitas Sumatera Utara
3.
Pengujian kesesuaian pemilihan jalur shortest path dengan nilai total jalur yang ditempuh.
4.2.1 Pengujian Shortest Path antara Node Terkecil dan Node Terbesar
Pada pengujian ini dipilih dua node sebagai data awal dan data akhir. Data awal merupakan node terkecil, yaitu dengan nilai 1 dan data akhir merupakan node terbesar, dengan nilai 125.
Pada pengujian ini, sistem dapat menentukan shortest path antara kedua node tersebut dengan melalui node-node berikut:
4.2.2 Pengujian dengan Shortest Path dengan Jalur Satu Arah
Pada pengujian ini dipilih node yang jalurnya menemui jalur satu arah. Tujuan pengujian ini diharapkan sistem dapat mengetahui jalur satu arah, sehingga dapat menemukan jalur lain untuk mencapai tujuan. Pengujian ini dilakukan dengan node awal dengan nilai 33 dan node akhir 78.
Pada pengujian ini, sistem dapat menentukan shortest path dengan jalur satu arah, dan sistem dapat menemukan jalur lain untuk mencapai tujuan. Berikut nodenode yang dilalui oleh shortest path:
33-34-59-70-79-89-90-78
Universitas Sumatera Utara
4.2.3 Pengujian Kesesuaian Pemilihan Jalur Shortest Path dengan Nilai Total Jalur yang Ditempuh
Pada pengujian ini, dipilih dua buah node dimana nantinya pada salah satu node akan ada pemilihan jalur dengan nilai yang lebih besar, namun dengan nilai total jalur yang ditempuh lebih kecil. Pengujian ini dilakukan pada node awal dengan nilai 22 dan node akhir dengan nilai 36. Pada pengujian ini, sistem nantinya harus memilih akan melalui jalur dengan node 22-35-36 atau melalui jalur dengan node 22-23-24-25-36.
Berikut besar nilai masing-masing jalur: 1. Jalur dengan node 22-35-36 Jalur 22-35
: 0.76264509
Jalur 35-36
: 0.44068858
Total
: 1.20333367
2. Jalur dengan node 22-23-24-25-36 Jalur 22-23
: 0.69939971
Jalur 23-24
: 0.28747265
Jalur 24-25
: 0.35873362
Jalur 25-26
: 0.37390443
Total
: 1.71951041
Pada pengujian ini, sistem dapat menentukan jalur yang harus dipilihnya untuk mendapatkan nilai total jalur terkecil, meskipun pada node awal jalur melalui jarak yang lebih besar. Pada hasil pengujian ini, shostest path melalui node-node berikut:
22-35-36
4.3 Tampilan Aplikasi Sistem
Aplikasi sistem ini hanya memiliki satu tampilan halaman, seluruh aktifitas user berada pada halaman ini. Pada setiap tampilan, user dapat langsung memilih node
Universitas Sumatera Utara
awal dan node akhir yang diinginkannya dan menekan tombol Cari Jalur untuk mencari shortest path antara kedua node yang telah dipilih. Bila user salah memilih node, user dapat menekan tombol Reset untuk mengulangi pemilihan node. Berikut adalah tampilan awal saat aplikasi dijalankan.
Gambar 4.1 Tampilan Awal Aplikasi
Pada tampilan awal ini, aplikasi akan menampilkan jalan-jalan yang menjadi jalur untuk shortest path. Jalan-jalan lain diabaikan pada saat ini. Untuk dapat melihat jalan-jalan yang lainnya user dapat melakukan zoom in dengan menggeser ke atas slider navigasi pada sisi kiri atas aplikasi. Berikut tampilan saat aplikasi pada posisi zoom in 1 x.
Universitas Sumatera Utara
Gambar 4.2 Tampilan Zoom in 1 x
Gambar 4.3 Pemilihan Node Awal
Universitas Sumatera Utara
Gambar 4.4 Pemilihan Node Akhir
Gambar 4.3 dan gambar 4.4 menunjukkan tampilan aplikasi saat pemilihan node awal dan node akhir dilakukan. Saat user memilih sebuah node, akan ditampilkan sebuah alert box yang menampilkan nilai node yang dipilih.
Saat user melakukan proses pencarian shortest path dengan menekan tombol Cari Jalur, aplikasi akan melakukan query terhadap jalur-jalur dan menampilkan hasil query pada aplikasi. Berikut tampilan aplikasi saat query ditampilkan.
Universitas Sumatera Utara
Gambar 4.5 Tampilan Query
Gambar 4.6 Tampilan Jalur Hasil Query
Universitas Sumatera Utara
Gambar 4.5 menunjukkan hasil query ditampilkan pada sebuah alert box. Disini ditunjukkan node-node yang dilalui oleh shortest path. Sedangkan pada gambar 4.6 ditampilkan jalur hasil query dengan titik-titik merah pada jalur yang dilalui.
Universitas Sumatera Utara
BAB V
KESIMPULAN DAN SARAN
5.1 Kesimpulan
Berdasarkan pembahasan dan evaluasi dari bab-bab terdahulu dan teori yang ada, maka dapat ditarik kesimpulan sebagai berikut:
1. Aplikasi Sistem Informasi Geografis dengan Shortest Path ini dapat menunjukkan jalur-jalur terpendek antara dua node yang diinginkan
2. Ka-Map tidak efesien untuk penggunaan aplikasi web-mapping dengan data spasial yang dinamis, karena ka-Map menggunakan sistem caching. Setiap ada perubahan data spasial, harus dilakukan penghapusan file cache untuk mendapatkan perubahan.
5.2 Saran
Saran-saran yang dapat digunakan untuk pengembangan skripsi ini adalah:
1. Diharapkan data telah lengkap diterima dan detail sehingga dapat dimasukkan ke dalam aplikasi yang telah ada.
2. Diharapkan pada aplikasi memiliki lebih banyak fitur, seperti pencarian lokasi.
3. Diharapkan aplikasi dapat dijalankan melalui internet, handphone, atau gadget lainnya
agar
user
lebih
mempermudah
akses
aplikasi.
Universitas Sumatera Utara
DAFTAR PUSTAKA
Aditya Pradhana, Bayu. 2007. Studi dan Implementasi Persoalan Lintasan Terpendek Suatu
Graf
Dengan
Algoritma
Dijkstra
dan
Algoritma
Bellman-Ford.
http://informatika.org/~rinaldi/Matdis/2006-2007/Makalah/Makalah060726.pdf. Diakses pada tanggal 19 Oktober 2008. Anindito iradat. 2000. Pengaruh Model Pemilihan Rute terhadap Matriks Asal-Tujuan yang
Diperoleh
dari
Informasi
Data
Arus
Lalu
Lintas.
http://digilib.lpmpdki.web.id/gdl.php?mod=browse&op=read&id=jbptitbppgdl-s2-2000-wiradatani-1751. Diakses pada tanggal 5 November 2008. Budi Prasetyo Bambang. Pengembangan Model Alternatif Pada Analisis Asal-Tujuan Transportasi Nasional. http://www.hubdat.web.id/literatur/tp/Mak-III-78.htm. Diakses pada tanggal 31 Oktober 2008. Farizki Wicaksono, Alfan. 2008. Modifikasi Dijkstra dengan Metode Ford untuk Mencari
Shortest
Path
pada
Graf
yang
Memiliki
Bobot
Negatif.
http://www.informatika.org/~rinaldi/Stmik/2007-2008/Makalah2008/ MakalahIF2251-2008-0607.pdf. Diakses pada tanggal 19 Oktober 2008. Ginanjar. 2008. Analisis Pencarian Jalur Jalan dalam Kampus ITB dengan Menggunakan
Basis
Data
Spasial
http://digilib.itb.ac.id/gdl.php?mod=browser&
3
Dimensi.
op=read&id=jbptitbpp-gdl-
ginanjarni-31037&q=Road. Diakses pada tanggal 14 Oktober 2008. Husein,
Rahmad.
Konsep
Dasar
Sistem
Informasi
Geografis.
http://ftsi.files.wordpress.com/2008/04/rahmat-sig.pdf. Diakses pada tanggal 19 Oktober 2008. http://digilib.petra.ac.id/ads-cgi/viewer.pl/jiunkpe/s1/elkt/2006/jiunkpe-ns-s1-200623400018-4590-file_vektor-chapter2.pdf. Diakses pada tanggal 20 Oktober 2008.
Universitas Sumatera Utara
http://www.informatika.org/~rinaldi/Matdis/2006-2007/bahankuliah2006.htm. Diakses pada tanggal 19 Oktober 2008. Iryanto. 2003. Pengantar Teori dan Aplikasi Graph. Medan: USU Press. Munir, Rinaldi. 2003. Matematika Diskrit. Edisi ke-2. Bandung: Informatika. Peraturan Pesiden No 85 tahun 2007 Tentang Jaringan Data Spasial Nasional. http://www.isdn.or.id/images/stories/perpres/Perpres_85_2007/pdf.
Diakses
pada tanggal 20 Oktober 2008. Ray Rizaldi, Mohammad. 2007. Pencarian Jalur Terpendek dalam GPS dengan Menggunakan Teori Graf. http://www.informatika.org/~rinaldi/Matdis/20062007/Makalah/Makalah0607-63.pdf. Diakses pada tanggal 17 Oktober 2008. Reza Arianto, Taufiq, Anggoro, Siwi, dan Rakhmawati. 2006. Strategi Greedy pada Kasus Pencarian Lintasan Terpendek. http://www.stttelkom.ac.id/staf/FAY/ kuliah/DAA/20052/Tugas1/pdfs/11-DAA%2020052%20113030008% 20113030030%20113030046%20Strategi%20Greedy%20pada%20Kasus%20 Pencarian%20Lintasan%20Terpendek.pdf. Diakses pada tanggal 20 Oktober 2008. Romenah. 2007. Sistem Informasi Geografi. http://elcom.umy.ac.id/elschool/muallim _muhammadiyah/file.php/1/materi/Geografi/SISTEM%INFORMASI%GEOGRA FI.pdf. Diakses pada tanggal 16 Oktober 2008.
Universitas Sumatera Utara
LAMPIRAN Tabel jarak antar node Node Koordinat Koordinat x y v1
457.6800
389.0750
v2
458.8850
391.4000
v3
461.5900
391.3550
v4
458.0500
391.3975
v5
463.6500
391.4825
v6
464.3500
391.4600
v7
465.0040
391.0950
v8
466.8600
391.1725
v9 v10
469.0000 458.4680
390.7800 391.9560
v11
458.4580
392.7240
v12
466.0330
393.3680
v13
465.9025
393.7700
v14
458.4725
394.3900
v15
460.1005
394.1500
Label
Node yang terhubung Sp Selayang v2 v4 Sp Kantor v1 v3 v10 v2 v4 v10 Sp Pos v1 v3 v5 v19 Asrama Haji v4 v6 Lap Sejati v5 v7 Sp Deli Tua v6 v8 v29 Sp Amplas v7 v9 v12 Tol Amplas v8 Sp Ringroad Setia v2 Budi v3 v11 v15 Pasti Pas v10 Ringroad v14 Pertamina SM v8 Raja v13 UISU v12 v30 Petronas Ringroad v11 v31 BCA Setia Budi v10 v16
Lanjutan tabel jarak antar node Node Koordinat Koordinat x y v70 v71 v72
463.1300 462.3840 458.5970
396.6950 396.4840 396.9820
v73
459.2850
396.950
v74
460.4470
396.8960
v75
460.8780
396.8660
v76 v77
462.3950 462.3990
396.7770 396.8880
v78 v79
462.5730 463.2290
396.9480 396.7830
v80 v81 v82
463.5100 463.6970 463.8150
396.9200 396.7570 396.7520
v83
464.2410
396.7050
v84 v85 v86 v87 v88
464.1970 464.1650 464.1420 464.0690 463.3330
396.8140 396.9100 396.9720 397.1610 397.0870
v89
463.2240
397.1190
v90
463.1020
397.1200
v91
463.2250
397.1790
v92 v93
464.0570 463.9750
397.1950 397.4320
Label
Node yang terhubung San Thomas v79 BCA Ismud v34 Sp Asrama v55 v73 v118 Pertamina Gatsu v72 v74 Sp Sei Sikambing v57 v75 v107 RS Advent v74 v77 Medan Plaza v71 Sp Medan Plaza v75 v76 Mdn Fair Plaza v77 Sp Jl Glugur v80 v89 v81 Palladium Plaza v82 Pancuran Lap v68 v84 Benteng Bank Mandiri v84 Lonsum Lap Merdeka v85 Hotel Deli v86 Kantor Pos v87 Telkom v92 Pertamina v80 Maulana Lubis Bundaran SIB v90 v88 Metro v78 v91 Sp Best Western v89 v115 BRI Deli Plaza v93 JW Marriot v91 v103 v104
