BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

2.1 Sistem Informasi Geografis Sistem Informasi Geografis (SIG) merupakan suatu sistem informasi berbasis komputer yang digunakan untuk menyajikan secara digital dan menganalisa penampakan geografis yang ada di permukaan bumi. Penyajian secara digital berarti mengubah keadaan menjadi bentuk digital. Setiap objek yang ada di permukaan bumi merupakan “geo-referenced”, yang merupakan kerangka hubungan database ke SIG. “Geo-referenced” menunjukkan lokasi suatu objek di ruang yang ditentukan oleh sistem koordinat, sedangkan database yaitu sekumpulan informasi tentang sesuatu dan hubungannya antar satu dengan lainnya. (Supriadi. 2007). Teknologi SIG berkembang pesat, teknologi ini terdiri dari perangkat lunak dan perangkat keras yang didesain untuk mengorganisir data yang berkaitan dangan bumi untuk menganalisis, memperkirakan dan gambaran kartografi. Informasi ruangan mengenai bumi sangat kompleks, tetapi pada umumnya data geografis mengandung 4 aspek penting, yaitu (Zhou, 1998): 1.

Lokasi-lokasi yang berkenaan dengan ruang, merupakan objek-objek ruang yang khas pada sistem koordinat (projeksi sebuah peta).

2.

Attribut, informasi yang menerangkan mengenai objek-objek ruang yang diperlukan.

3.

Hubungan ruang, hubungan logis atau kuantitatif diantara objek-objek ruang.

4.

Waktu, merupakan waktu untuk memperoleh data, data atribut dan ruang.

SIG merupakan suatu rancangan sistem informasi untuk mengerjakan data koordinat geografis atau berunsur ruang. Teknologi SIG menyatu dengan operasi

Universitas Sumatera Utara

7

database seperti pencarian data dan analisa statistik serta analisis geografis yang disajikan dalam bentuk peta. Kemampuan SIG ini banyak digunakan secara luas misalnya untuk menjelaskan kejadian, memperkirakan hasil dan perencanaan strategis (Supriadi, 2007). Ada beberapa alasan yang mendasari mengapa perlu menggunakan SIG, menurut Anon (2003, dalam As Syakur 2007) alasan yang mendasarinya adalah: a. SIG

sangat

efektif

dalam

membantu

proses-proses

pengembangan,

pembentukan, atau perbaikan peta b. SIG dapat digunakan sebagai alat bantu utama yang effektif, menarik, dan menantang dalam usaha-usaha untuk meningkatkan pemahaman, pengertian, dan pendidikan mengenai ide atau konsep lokasi, ruang (spasial), kependudukan dan unsur-unsur geografis yang terdapat dipermukaan bumi berikut data atribut terkait yang menyertainya. c. SIG dapat memberikan gambaran yang lengkap dan komprehensif terhadap suatu masalah nyata yang terkait spasial permukaan bumi. d. SIG menggunakan baik data spasial maupun atribut secara terintegrasi hingga sistemnya dapat menjawab baik pertanyaan spasial maupun non-spasial, memiliki kemampuan analisis spasial dan non-spasial. e. SIG memiliki kemampuan yang sangat baik dalam memvisualkan data spasial berikut atribut-atributnya. f. SIG memiliki kemampuan untuk menguraikan unsur-unsur yang terdapat di permukaan bumi ke dalam bentuk layer, tematik, atau coverage data spasial. g. SIG dapat menurunkan informasi secara otomatis tanpa keharusan untuk selalu melakukan interpretasi secara manual. Dengan demikian, SIG dengan mudah dapat menghasilkan data spasial tematik yang merupakan (hasil) turuan dari data spasial yang lain (primer) dengan hanya memanipulasi atribut-atributnya.

2.2 Google Maps Google Maps adalah layanan aplikasi peta online yang disediakan oleh Google secara gratis. Layanan peta Google Maps secara resmi dapat diakses melalui situs http://maps.google.com. Pada situs tersebut dapat dilihat informasi geografis pada


8

hampir semua permukaan di bumi kecuali daerah kutub utara dan selatan. Layanan ini dibuat sangat interaktif, karena di dalamnya peta dapat digeser sesuai keinginan pengguna, mengubah level zoom, serta mengubah tampilan jenis peta. Google Maps mempunyai banyak fasilitas yang dapat dipergunakan misalnya pencarian lokasi dengan memasukkan kata kunci, kata kunci yang di maksud seperti nama tempat, kota, atau jalan, fasilitas lainnya yaitu perhitungan rute perjalanan dari satu tempat ke tempat lainnya (Amri, 2012).

2.2.1 Cara Kerja Google maps Google Maps dibuat dengan menggunakan kombinasi dari gambar peta, database, serta obyek-obyek interaktif yang dibuat dengan bahasa pemrograman HTML, Javascript dan AJAX, serta beberapa bahasa pemrograman lainnya (Cita, 2008). Gambar-gambar yang muncul pada peta merupakan hasil komunikasi dengan database pada web server Google untuk menampilkan gabungan dari potonganpotongan gambar yang diminta. Keseluruhan citra yang ada diintegrasikan ke dalam database pada Google Server, yang nantinya akan dapat dipanggil sesuai kebutuhan permintaan. Bagian-bagian gambar map merupakan gabungan dari potongan gambargambar bertipe PNG yang disebut tile yang berukuran 256 x 256 pixel seperti gambar berikut (Amri, 2012).

Gambar 2.1 Pembagian gambar peta sebesar 256 x 256 pixel


9

Tiap-tiap potongan gambar diatas, mewakili gambar tertentu dalam longitude, latitude dan zoom level tertentu. Latitude adalah garis yang melintang di antara kutub utara dan kutub selatan, yang menghubungkan antara sisi timur dan barat bagian bumi. Sedangkan longitude adalah garis membujur yang menghubungkan antara sisi utara dan sisi selatan bumi (kutub). Kode Javascript yang digunakan untuk menampilkan peta Google Maps diambil dari link URL. Jadi untuk menampilkan peta suatu lokasi yang diinginkan, dapat dengan cara mengirimkan URL yang diinginkan, misalnya:

http://maps.google.com/?ie=UTF8&ll=6.500899,106.918945& spn=4.327078,4.938354&z=8

Berdasarkan Link URL tersebut maka ie=UTF8 merupakan karakter encoding untuk map, ll=-6.500899,106.918945, adalah posisi titik tengah peta yaitu latitude (lintang) dan longitude (bujur) dari peta yang ditampilkan, pada link diatas posisi titik tengah peta pada latitude: -6.500899 dan longitude: 106.918945. Sedangkan spn=4.327078,4.938354 merupakan rentang dari latitude dan longitude-nya dan z=8, adalah tingkatan/level zoom peta.

2.2.2 Google Maps API Google Maps adalah layanan pemetaan berbasis web service yang disediakan oleh Google dan bersifat gratis, yang memiliki kemampuan terhadap banyak layanan pemetaan berbasis web. Google Maps juga memiliki sifat server side, yaitu peta yang tersimpan pada server Google dapat dimanfaatkan oleh pengguna (Cita, 2008). API atau Application Programming Interface merupakan suatu dokumentasi yang terdiri dari interface, fungsi, kelas, struktur dan sebagainya untuk membangun sebuah perangkat lunak. Dengan adanya API ini, maka memudahkan programmer untuk “membongkar” suatu software untuk kemudian dapat dikembangkan atau diintegrasikan dengan perangkat lunak yang lain. API dapat dikatakan sebagai penghubung suatu aplikasi dengan aplikasi lainnya yang memungkinkan programmer menggunakan sistem function. Proses ini dikelola melalui operating system.


10

Keunggulan dari API ini adalah memungkinkan suatu aplikasi dengan aplikasi lainnya dapat saling berhubungan dan berinteraksi. Bahasa pemrograman yang digunakan oleh Google Maps yang terdiri dari HTML, Javascript dan AJAX serta XML, memungkinkan untuk menampilkan peta Google Maps di website lain (Amri, 2012). Google juga menyediakan layanan Google Maps API yang memungkinkan para pengembang untuk mengintegrasikan Google Maps ke dalam website masingmasing dengan menambahkan data point sendiri. Google Maps API adalah suatu library yang berbentuk javascript yang berguna untuk memodifikasi peta yang ada di Google Maps sesuai kebutuhan. Untuk membangun aplikasi yang memanfaatkan Google Maps di desktop dan mobile device maka akan digunakan Google Maps Javascript API v3 yang memiliki keunggulan lebih cepat dari versi sebelumnya (Google Developers, 2012). Dengan menggunakan Google Maps API, Google Maps dapat ditampilkan pada web site eksternal. Agar aplikasi Google Maps dapat muncul di website tertentu, diperlukan adanya API key. API key merupakan kode unik yang digenerasikan oleh Google untuk suatu website tertentu, agar server Google Maps dapat mengenali. Script Google Maps API dapat dilihat pada tabel 2.1.

Tabel 2.1 Script kode Google Maps API <scripttype=”text/javascript” src=”http://maps.google.com/maps?file=api&v=2&sensor=false& key=ABQIAAAAbE7c_nBHqt2MsYavLihx9hQJ7kqb6IJHXd0Q5wX6KEaY9g0u mhROwx63Z3Gq2UYSM8sC7Ngl45s6nw“>

Kode yang tercetak merah adalah kode dari Google Maps API. Untuk mendapatkan

kode

itu

dapat

mendaftar

pada

http://code.google.com/apis/maps/signup.html agar website mendapatkan kunci untuk mengakses API pada google. Key akan berbeda untuk setiap website yang didaftarkan ke google maps.


11

2.3 Android Android merupakan open source platform untuk mobile devices yang di kembangkan oleh google bersama Open Handset Alliance (OHA) yaitu aliansi perangkat selular terbuka yang terdiri dari 47 perusahaan hardware, software dan perusahaan telekomunikasi ditujukan untuk mengembangkan standar terbuka bagi perangkat selular. Tujuan aliansi tersebut yaitu untuk mengakselerasi pembaharuan dalam mobile dan menawarkannya ke konsumen yang lebih kaya, dan sedikit mahal (Gargenta, 2011). Android sistem operasi berbasis linux yang mencakup sistem operasi, middleware dan aplikasi (Safaat, 2012). Android menawarkan sebuah lingkungan yang berbeda untuk pengembang. Setiap aplikasi memiliki tingkatan yang sama. Android tidak membedakan antara aplikasi inti dengan aplikasi pihak ketiga (Safaat H, 2011). API yang disediakan menawarkan akses ke hardware, maupun data-data ponsel sekalipun, atau data sistem itu sendiri. Pengguna dapat menggantikannya dengan aplikasi pihak ketiga dengan cara menghapus aplikasi inti. Sedangkan android SDK (Software Development Kit) menyediakan API dan Tools yang diperlukan untuk mengembangkan aplikasi pada platform Android dengan menggunakan bahasa pemrograman Java. Untuk pengembang hal yang perlu diperhatikan yaitu tidak membutuhkan sertifikasi untuk menjadi pengembang Android. Bagi para pengembang ingin menempatkan dan menjual aplikasi yang telah dibuatnya maka Android telah menyediakan Android market. Hal menarik lainnya yang menjadi pembeda Android dengan yang lain adalah (Ginting, 2014): 

Pertukaran data dan komunikasi antar proses



Aplikasi servis yang berjalan di background



Dukungan Google Maps Menurut Margenta, ada beberapa kelebihan android antara lain sebagai

berikut: 

Android adalah comprehensive platform, softwarenya lengkap.



Open source platform, bebas pengembangan tanpa dikenakan biaya terhadap sistem karena berbasiskan linux.


12



Android adalah purpose-built untuk mobile device. Desain dari Android berasal dari waktu mendatang yang dapat diduga.



Android juga tidak memakan memori yang terlalu banyak sehingga user tidak terlalu khawatir terhadap software yang memorinya terbatas. Ada dua cara untuk membangun atau membuat aplikasi berbasis Android,.

Pertama, memiliki perangkat telepon seluler yang berbasis Android langsung. Kedua, menggunakan emulator yang sudah disediakan oleh Google. Sebelum memulai membangun aplikasi berbasis Android, diperlukan beberapa perangkat, antara lain : 

The Eclipse IDE.



Sun’s Java Development Kit (JDK).



The Android Software Developer’s Kit (SDK).



The Android Developer Tool (ADT).



Plug-in Eclipse. Pengembangan pembuatan aplikasi berbasis Android dengan memanfaatkan

Android SDK dapat dilakukan pada salah satu sistem operasi seperti Windows (XP, Vista dan 7), Linux dan Mac OS X (Elian & Mazharuddin, 2012).

2.4 GPS GPS (Global Positioning System) merupakan sistem untuk menentukan posisi dan navigasi secara global dengan menggunakan satelit. Nama asli dari GPS adalah NAVSTAR GPS (Navigation Satellite Timing and Ranging Global Positioning System), mempunyai tiga segmen yaitu : satelit, pengontrol, dan penerima (Winardi, 2006). 

Satelit bertugas untuk menerima dan menyimpan data yang ditransmisikan oleh stasiun – stasiun pengontrol, menyimpan dan menjaga informasi waktu berketelitian tinggi (ditentukan dengan jam atomic di satelit), dan memancarkan sinyal dan informasi secara continue ke pesawat penerima dari pengguna.


13



Pengontrol bertugas mengendalikan dan mengontrol satelit dari bumi baik untuk mengecek kesehatan satelit, penentuan dan prediksi orbit dan waktu, sinkronisasi antar satelit, dan mengirim data satelit.



Penerima bertugas menerima data dari satelit dan memprosesnya untuk menentukan posisi (posisi tiga dimensi yaitu koordinat di bumi plus ketinggian), arah, jarak dan waktu yang diperlukan oleh pengguna. Cara kerja GPS dapat dilihat pada gambar 2.2 di bawah ini.

Gambar 2.2 Cara Kerja GPS Dari gambar 2.2 maka cara kerja GPS yaitu konstelasi satelit GPS memancarkan sinyal posisi satelit. Sinyal tersebut “ditangkap” oleh penerima sinyal GPS. Penerima GPS yaitu user yang menggunakan mobile phone. Dengan menghitung waktu tempuh sinyal dari 3 GPS, maka posisi didapat. Lokasi informasi tersebut dikirim melalui internet yang dapat diakses melalui mobile phone.

2.5 Client Server Client server merupakan salah satu model komunikasi 2 komputer atau lebih yang berfungsi melakukan pembagian tugas. Client bertugas untuk melakukan input, update, penghapusan, dan menampilkan data sebuah database. Sedangkan server bertugas menyediakan pelayanan untuk melakukan manajemen, yaitu menyimpan dan mengolah database (Wahana Komputer, 2010). Ada beberapa model arsitektur client server, diantaranya adalah 1-Tier (standalone), 2-Tier, dan n-Tier. Arsitektur 1-Tier yaitu sebuah komputer dapat


14

mengakses sebuah database dari komputer sendiri. Dengan kata lain, aplikasi antarmuka user dan aplikasi database terdapat pada komputer yang sama. Arsitektur 2-Tier merupakan model yang membagi tugas antara komputer client dan komputer server. Komputer client bertugas menyediakan antarmuka untuk user, permintaan data ke server, serta pemrosesan data. Komputer server bertanggung jawab terhadap penyimpanan, pengelolaan, serta melayani permintaan akses data. Arsitektur n-Tier berarti membagi komponen menjadi n entitas, yaitu 1 tier client dan n-1 tier server. Bagian client bertugas menyediakan antarmuka aplikasi, sedangkan bagian server bertugas menyediakan data. 2.6 Definisi Graf Graf merupakan pasangan himpunan (V,E), ditulis dengan notasi G=(V,E), yang dalam hal ini V adalah himpunan tidak-kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. (Munir. 2005). Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpul harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi (edges) pun dinamakan graf trivial.

2.6.1. Jenis-jenis Graf Graf dapat dikelompokkan menjadi beberapa kategori (jenis) tergantung pada sudut pandang pengelompokannya. Pengelompokan graf dapat dipandang berdasarkan ada tidaknya sisi (edges) ganda atau sisi (edges) kalang, berdasarkan jumlah simpul, atau berdasarkan orientasi arah pada sisi (edges). Berdasarkan ada tidaknya gelang (loop) atau sisi (edges) ganda pada suatu graf, maka secara umum dapat digolongkan menjadi dua jenis: a. Graf sederhana (simple graph). Graf yang tidak mengandung gelang (loop) maupun sisi (edges) ganda dinamakan graf sederhana. G1 pada Gambar 2.2 (a) adalah contoh graf sederhana yang merepresentasikan jaringan komputer. Pada graf sederhana, sisi adalah pasangan tak-terurut (unordered pairs). Jadi, menuliskan (u,v) sama saja dengan (v,u). Kita dapat juga mendefenisikan graf sederhana G =


15

(V,E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan pasang tak-terurut yang berbeda yang disebut sisi.

b. Graf tak-sederhana (unsimple-graph). Graf yang megandung sisi (edges) ganda atau gelang (loop) dinamakan graf tak-sederhana (unsimple graph). Ada dua macam graf tak-sederhana, yaitu: a. Graf Ganda (multigraph), adalah graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah. G2 seperti pada Gambar 2.2 (b) adalah contoh graf ganda. b. Graf Semu (pseudograph), adalah graf yang mengandung gelang (loop). Graf semu lebih umum dari pada graf ganda, karena sisi (edges) pada graf semu dapat terhubung ke dirinya sendiri. G3 seperti pada Gambar 2.2 (c) adalah contoh graf semu.

Gambar 2.3 tiga buah graf (a) Graf sederhana, (b) Graf ganda, (c) Graf semu Sisi pada graf dapat mempunyai orientasi arah (Munir. 2012). Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis yaitu: a. Graf tak-berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (u, v) = (v, u) adalah sisi yang sama. Tiga buah graf seperti pada gambar 2.2 adalah graf tak-berarah. b. Graf berarah (directed graph atau digraph) Graf yang sisinya diberikan orientasi arah disebut sebagai graf berarah atau sisi berarah sering disebut dengan busur (arc). Pada graf berarah, (u, v) dan (v,


16

u) menyatakan dua buah busur yang berbeda, dengan kata lain (u, v) ≠ (v, u). Untuk busur (u, v), simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex). Pada gambar 2.3 adalah contoh gambar graf berarah.

Gambar 2.4 (a) Graf berarah, (b) Graf ganda berarah.

2.7 Lintasan Terpendek (Shortest Path) Lintasan terpendek merupakan persoalan optimasi. Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya ada nilai atau bobot. Bobot pada sisi graf dapat dinyatakan sebagai jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya. Asumsi yang digunakan adalah bahwa semua bobot bernilai positif (Munir. 2012). Ada beberapa macam persoalan lintasan terpendek, antara lain: 

Lintasan terpendek antara dua buah simpul tertentu.



Lintasan terpendek antara semua pasangan simpul.



Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.



Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.

2.8 Algoritma Bellman Ford Dalam proses routing (perutean), yang biasa dilakukan adalah menggunakan algoritma untuk menentukan path terpendek dalam tiap-tiap node untuk mendapatkan path secara efisien. Salah satu algoritma yang digunakan adalah algoritma BellmanFord. Algoritma

Bellman–Ford

adalah

algoritma

untuk

menyelesaikan


17

permasalahan lintasan terpendek dengan sumber tunggal (Purwanto, 2008). Algoritma Bellman–Ford dikembangkan oleh Richard Bellman dan Lester Ford. Algoritma Bellman-Ford merupakan shortest path terpendek di mana algoritma ini dapat menentukan path terpendek dari seluruh node menuju satu node tertentu. Algoritma Bellman-Ford termasuk jenis perutean distance vektor, berarti dia memiliki informasi dari router tetangganya (quora, 2014). Secara umum, langkah-langkah algoritmanya adalah sebagai berikut (Cormen. 2009): 

Tentukan vertex source dan daftar seluruh vertices maupun edges.



Assign nilai untuk distance dari vertex source = 0, dan yang lain infinite .



Mulailah iterasi terhadap semua vertices yang dimulai dari vertex source,



Untuk menentukan distance dari semua vertices yang berhubungan dengan vertex source dengan formula seperti berikut ini : -

U = vertex asal

-

V = vertex tujuan

-

UV = Edges yang menghubungkan U dan V

-

Jika distance V, lebih kecil dari distance U + weight UV maka distance V, diisi dengan distance U + weight UV

-

Lakukan hingga semua vertices terjelajahi

Contoh Seseorang berada di lokasi S ingin menuju ke lokasi T. Tentukan rute yang paling dekat menurut algoritma Bellman-Ford. A

1

B

5

S

3

2

7

1

T

10 C

3

D

Gambar 2.5 contoh rute Langkah 1 Buat vertex awal = 0 dan vertex lainya dengan nilai tak terhingga


18

∞

∞

1

5

3

0

2

∞

7

1

10

∞

∞

3

Gambar 2.6 langkah 1 Hasil dari gambar 2.6 dapat dilihat pada tabel 2.2. Tabel 2.2 Tabel Hasil langkah 1

d [V]

S

A

B

C

D

T

0

∞

∞

∞

∞

∞

Pi [V] Langkah 2 Hitung semua vertex. - Vertex S = 0 - Vertex A = 5 melewati vertex S A 5/S 5

S

- Vertex B = 6 melewati vertex A A 5/S

1

B 6/A

5

S

1 C


19

- Vertex C = 1 melewati vertex S

A 5 S

1 C 1/S

- Vertex D = 13 melewati vertex B A

1

B

5

S

7

1 D 13/B

C

- Vertex T = 9 melewati vertex B A

1

B

5

3

S

9/B

7

1 C

D

Hasil dari langkah 2 dapat dilihat pada tabel 2.3 Tabel 2.3 Hasil langkah 2 S

A

B

C

D

T

d [V]

0

5

6

1

13

9

Pi [V]

0

S

A

S

B

B


20

Langkah 3 Hitung kembali semua vertex yang belum terlewati A 5/S

1

B 6/A

5

3

S

2

7

C 1/S

D 13/B

1

T 9/B

10 3

Gambar 2.7 Hasil langkah 2

- Vertex S = 0 - Vertex A = 3 melewati vertex C A 3/C 5 S

2 1 C 1/S

- Vertex B = 4 melewati vertex A A 3/C

1

B 4/A

5

S

2

1 C 1/S

- Vertex D = 4 melewati vertex C A 3/C

1

B 4/A

5

S

2

7

1 C 1/S

3

D 4/C

- Vertex T = 14 melewati vertex D dan7 jika melewati vertex B


21

A 3/C

B 4/A

1

A 3/C

5 S

3 2

5

T 7/B

7

1

3

S

10 C 1/S

2

T 14/D

7

1

10

D 4/C

3

B 4/A

1

C 1/S

D 4/C

3

Hasil dari langkah 3 dapat dilihat pada tabel 2.4.

Tabel 2.4. Hasil langkah 3 S

A

B

C

D

T

d [V]

0

3

4

1

4

7

Pi [V]

0

C

A

S

C

B

Tampilan hasil yang telah di uji dengan menggunakan Algoritma Bellman Ford untuk mendapatkan rute yang pendek dapat dilihat seperti pada gambar 2.8.

A 3/C

1

B 4/A

5

S

3

2

7

C 1/S

D

1

T 7/B 10

3

Gambar 2.8 Rute pendek dengan Bellman Ford Dari gambar 2.8 maka jarak user yang berada di lokasi S menuju lokasi T adalah 7 km dengan rute nya S – C – A – B – T.


22

Flowchart dari algoritma Bellman-Ford adalah

start

Asumsi verte awal 0 vertex lainya dengan nilai ∞

Cari nilai vertex tetangganya

Hitung jarak vertex ke tujuan TIDAK Mencari jarak terpendek

TIDAK

YA

Update nilai vertex yang telah di cek

Apakah semua verex telah di cek

YA End

Gambar 2.9 Flowchart Bellman-Ford.

2.9. Penelitian Terdahulu Berbagai penelitian terdahulu tentang pencarian jarak terpendek menggunakan algoritma Bellman-Ford dan algoritma pencarian jarak terpendek lainnya.Selain itu penelitian terdahulu juga membahas tentang SPBU dan aplikasi berbasis android. Adapun penelitian terdahulu dapat dilihat pada Tabel 2.5 berikut ini:


23

Tabel 2.5 Penelitian Terdahulu No 1.

2.

Judul

Peneliti

PerancanganAplikasi Pencarian Rute Terpendek SPBU Di Kota Bandung Berbasis Android

Rizki Fakhurozi (2012)

Aplikasi Algoritma Kristanto Bellman Ford Dalam (2012) Meminimumkan Biaya Operasional Rute Penerbangan

Metode ______

Keterangan Sistem ini dapat menetukan Pencarian

rute

terpendek

SPBU di kota Bandung

BellmanFord

Sistem

ini

berhasil

mengimplemtasikan algoritma

Bellman-Ford

untuk meminimukan biaya rute penerbangan

3.

Sistem Pendukung

Arif

Floyd

Sistem ini dapat dijadikan

Keputusan Pemilihan

Fahmi

Warshall

sumber informasi, namun

Alat Transportasi

2012

waktu eksekusi yang sedikit

Umum Kota Malang

lama

dalam

memberikan

rekomendasi.

Semakin

banyak

semakin

verteks,

lama proses pencarian.

4.

Aplikasi Rekomendasi Pencarian

Ginting dan (2014) Rute

A*

Menampilkan rekomendasi

(A-Star)”

satu angkot dan dua angkot. Sistem

ini

menampilkan

Terpendek 5. 4 Angkutan

rute- rute mana saja yang

Kota di Medan 4

dilalui angkot.

Peneliti menggunakan algoritma Bellman-Ford dalam rekomendasi rute SPBU terdekat tersebut karena algoritma Bellman-Ford mengecek semua vertex maka pencarian rute terdekat akan menghasilkan rute yang lebih akurat dan BellmanFord akan merekomendasi jalan lain untuk menuju ke lokasi tujuan. Selain itu


24

peneliti juga menggunakan GPS untuk menentukan posisi awal user sehingga akan memudahkan pengguna akan ketidaktahuan posisi di mana si user berada.


BAB 2 LANDASAN TEORI

Recommend Documents