## Sistem Informasi Geografis Penentuan Rute Terpendek Lokasi Villa Menggunakan Algoritma Floyd Warshall
Arial 11
Hendro Wijayanto 1) ; Didik Nugroho 2) ; Beni Aryo Santoso 3) 1,2,3) Program Studi Teknik Informatika, STMIK Sinar Nusantara
1) hendro@sinus.ac.id ; 2) didik@sinus.ac.id; 3) beni.aryo95@gmail.com ……. ……. 11

## ABSTRACT
Tawangmangu  district  has  many  types  of  villa  that  can  be  welcome  for  the  local  people and the community itself. Information about  the location of  villa needed by tourists and also the general  public  is  the  route  information  to  the  villa  in  Tawangmangu  district.  The  aim  of  the research  is  to  apply  Floyd  Warshall  algorithm  in  finding  the  shortest  route  for  villa  in Tawangmangu district which has 150 and about 30 in the Web interface with the help of Google Maps API. The closest villa location to the Grojokan sewu tourist  is the Indra Sari villa with 245 meters of yield. For the comparisons, Google Maps got 80% result of the 30 different test paths and  due  diligence  with  respondents  showed  a  feasibility  rate  of  88,75%  indicating  that  the application  is  well-deserved  by  the  user.  Floyd  Warshall  algorithm  is  applied  because  the principle of the algorithm Floyd Warshall is the principle of optimality. The result is an application that can show the shortest route, along with from the starting location to the destination location of the villa.
Keywords: Geographic Information Systems, Floyd Warshall, Shortest Route

## I. PENDAHULUAN
Kecamatan  Tawangmangu  adalah  salah satu kecamatan penuh dinamika yang mempunyai  berbagai  tempat  wisata  dan berbagai macam penginapan. Memiliki potensi besar untuk mendatangkan banyak wisatawan baik  lokal  maupun  mancanegara.  Kecamatan Tawangmangu  mempunyai  sekitar  150  Villa yang  tersebar  dibeberapa  kelurahan  dengan rincian seperti Tabel 1 berikut ini.

## Tabel 1. Sebaran Villa
Kelurahan Villa Pribadi Villa Disewakan Kalisoro 6 4 Blumbang 5 5 Tawangmangu 4 5
Dalam  membangun  tempat  wisata  dan penginapan, banyak hal yang perlu diperhatikan,  diantaranya  mengenai  sektor transportasi.  Transportasi  merupakan  sarana vital yang menunjang perjalanan suatu tempat wisata  dan  penginapan.  Letak  geografis Kecamatan  Tawangmangu  yang  memiliki jalan perkampungan dengan lebar jalan relatif sempit membuat beberapa kendaraan kesulitan  menuju  destinasi  tujuan  wisata  atau penginapan.  Sehingga  untuk  menempuhnya harus memutar atau memilih jalan yang lain.
Di  sisi  lain,  pemanfaatan  fasilitas  Global Positioning System (GPS) belum terlalu efektif untuk  memberikan  petunjuk  arah.  Terkadang
hasil dari GPS tidak sesuai dengan kenyataan.  Misalnya  jalan  yang  ditunjukkan oleh  sistem  GPS  hanya  dapat  dilalui  oleh kendaraan kecil atau jalan setapak.
Dari  permasalahan  tersebut  dapat  ditarik masalah  bagaimana  membuat      teknologi yang membantu pengguna dalam menemukan  lokasi  Villa  dan  statusnya. Diantaranya  menggunakan  teknologi  Sistem Informasi  Geografi.  Geographic  Information System  atau  dikenal  juga  dengan  GIS/SIG (Sistem  Informasi  Geografis)  adalah  sistem berbasis komputer untuk mengelola, menganalisis  dan  menyebarkan  informasi geografis [1][2].
Google  Maps  yang  sudah  lumayan canggih tapi masih kurang dalam mengulas di wilayah
Kecamatan Tawangmangu diantaranya  kurangnya  informasi  villa  yang  di sewakan  dan  tidak  disewakan  /  villa  pribadi dan  dalam  SIG  yang  dibangun  ini  akan adanya  informasi  serta  mengkategorikan  villa disewakan  dan  tidak  disewakan  /  villa  pribadi tersebut  nantinya  akan  ditanamkan  algoritma yang  berfungsi  sebagai  pencari  rute  optimum dari lokasi asal ke lokasi villa yang di tuju, dan algoritma  yang  digunakan  adalah  Floyd- Warshall.
Pemilihan  algoritma  tersebut  dikarenakan algoritma ini merupakan bagian dari algoritma dinamik  yang  dapat  mencari  semua  lintasan terpendek masing-masing antara tiap kemungkinan  pasang  tempat  yang  berbeda
( All-pairs Shortest Path Problems ) dan sangat efektif  digunakan  dalam  menangani  masalah rute optimum [3].
Dari masalah diatas inilah yang mendasari pembuatan aplikasi penentuan rute terpendek lokasi  villa  menggunakan  algoritma  Floyd Warshall  berbasis  Web  GIS  di  Kecamatan Tawangmnagu, yang akan di tampilkan dalam sebuah  web  dengan  bantuan  interface  dari Google  Maps  API.  Perangkat  lunak  ini  akan menampilkan berbagai villa yang ada dikecamatan  Tawangmangu,  dan  menuntun user harus menginputkan lokasi awal (keberadaan)  dan  lokasi  akhir  (tujuannya). Rute optimum yang dimaksud adalah rute/jalan  tercepat  yang  akan  dilalui  dengan kendaraan.  Dengan  terbentuknya  aplikasi  ini nanti diharapkan masyarakat pendatang dapat memangkas  waktu  tempuh  dalam  pemilihan villa,  serta  memperoleh  informasi  detail  dari villa di Kecamatan Tawangmangu.

## II. TINJAUAN PUSTAKA
Application  Programming  Interface  atau API  adalah  sekumpulan  perintah,  fungsi,  dan protokol yang dapat digunakan oleh programmer  saat  membangun  perangkat lunak  untuk  sistem  operasi  tertentu.  Menurut web Google Maps for Bussines, Google Maps API adalah kumpulan API yang memungkinkan  pengguna  menghamparkan data  pada  Google  Maps  yang  disesuaikan. Pengguna  dapat  membuat  aplikasi  web  dan seluler  menarik  dengan  platform  pemetaan canggih dari Google termasuk basis data citra satelit,  pemandangan  jalan,  profil  ketinggian, petunjuk  arah  mengemudi,  peta  dengan sentuhan  gaya,  demografi,  analisis,  dan tempat yang luas [4].
Google  Maps  merupakan  SIG  yang berbasis  internet  yang  diberikan  Google secara  gratis,  termasuk  di  dalamnya  website Google Maps (http://maps.google.com), Google  Ride  Finder,  Google  Translate,  dan peta  yang  dapat  disisipkan  pada  website  lain melalui  Google  Maps  API.  Saat  ini  Google Maps adalah layanan pemetaan berbasis web yang  popular.  User  membuat  aplikasi  dengan menambahkan  layanan  Google  Maps  ke website  yang  dibuatnya.  Google  Maps  API dapat  ditambahkan  ke  sebuah  website menggunakan JavaScript. API tersebut menyediakan  banyak  fasilitas  dan  utilitas untuk  memanipulasi  peta  dan  menambahkan konten  ke  peta  melalui  berbagai  layanan, memungkinkan  user  untuk  membuat  aplikasi peta  yang kuat  pada sebuah  website.  Namun
untuk  dapat  mengakses  Google  Maps, terlebih dahulu user harus melakukan pendaftaran API key dengan data pendaftaran berupa  nama  domain  web  yang  kita  bangun. Google Map API mengijinkan kepada pengguna untuk membangun aplikasi enterprise di dalam websitenya.
Graf merupakan struktur data yang paling umum.  Jika  struktur  linear  memungkinkan pendefinisian keterhubungan sikuensial antara entitas data, struktur data tree memungkinkan pendefinisian  keterhubungan  hirarkis,  maka struktur  graph  memungkinkan  pendefinisian keterhubungan  tak  terbatas  antara  entitas data.  Graf  sering  digunakan  dalam  berbagai disiplin  ilmu,  seperti  pengelolaan  intertautan jaringan,  memetakan  jalan  raya  antarkota, memodelkan  objek  tiga  dimensi,  hingga pemetaan DNA pada manusia [5].
Dalam  penelitian  [6]  telah  dilakukan penelitian  untuk  menentukan  rute  terpendek ke  obyek  wisata  populer  di  Kota  Semarang. Floyd  Warshall  digunakan  untuk  menghitung jarak  simpul  antar  titik  obyek  wisata.  Adapun didalamnya belum menggunakan peta, sehingga  rute  hanya  berdasarkan  jarak  tanpa menggambarkan  titik  dan  jalur  dalam  bentuk interface peta.
Pemodelan  Floyd-Warshall  juga  dapat digunakan  untuk  mencari  titik  terdekat  dalam pencarian kendaraan di tempat parkir. Sehingga dapat mempersingkat waktu pencarian,  mengoptimalkan  daya  tampung parkir,  dan  memudahkan  pemilik  kendaraan dalam  menentukan  blok  mana  harus  dilewati untuk menemukan kendaraannya [7].
Algoritma  Floyd  Warshall  diciptakan  oleh R.  Floyd  pada  tahun  1962.  Algoritma  Floyd Warshall  adalah  salah  satu  pemrograman dinamis,  yaitu  suatu  metode  yang  melakukan pemecahan  masalah  dengan  memandang solusi  yang  akan  diperoleh  sebagai  suatu keputusan  yang  saling  terkait.  Artinya  solusi- solusi  tersebut  dibentuk  dari  solusi  yang berasal  dari  tahap  sebelumnya  dan  ada kemungkinan  solusi  lebih  dari  satu.  Floyd Warshall merupakan algoritma untuk pencarian  lintasan  terpendek  pada  suatu  graf berbobot ( weighted graph ). Algoritma ini dapat melakukan analisis dan penyelesaian kerumitan suatu proses [8].

## Gambar 1. Floyd Warshall
Alur Algoritma Floyd Washall berdasarkan gambar yaitu:
1.  Yang pertama dilakukan adalah menginputkan  lokasi  awal  dan  lokasi tujuan sabagai data.
2.  Pada  iterasi  1,  setiap  sel  matriks dilakukan  pengecekan  apakah  antar  dua titik  lebih  besar  dari  penjumlahan  antar titik asal ke titik tujuan (titik tujuan = iterasi k-1)  dengan  jarak  titik  asal  (titik  asal  = iterasi  k-10  ke  tujuan.  Dengan  kata  lain W[i,j] > W[i,k] + W[k,j].
3.  Jika  iya  maka  jarak  yang  digunakan adalah jarak antar dua titik diganti dengan penjumlahan antar titik asal ke (titik tujuan = iterasi k-1) dengan jarak titik asal (titik a = iterai 1) ke titik tujuan W[i,k] + W[k,j].
4.  Jika  tidak  maka  jarak  yang  digunakan yaitu dua titik W[i,j].
5.  Proses  iterasi  dilakukan  hingga  iterasi terakhir  (iterasi  terakhir  =  total  titik  atau node / k-n).
6.  Hasil  terakhir  berupa  jarak  optimal  dar setiap lokasi awal menuju lokasi tujuan.
Pengujian dilakukan menggunakan pengujian  validitas  dan  pengujian  kepuasan pengguna. Pengujian validitas dilakukan untuk mengukur seberapa perbedaan antara aplikasi  yang  telah  dirancang  dengan  Google Maps.  Sedangkan  pengujian  pengukuran kepuasan  digunakan  untuk  melihat  kepuasan pengguna aplikasi.
III.  METODE PENELITIAN 3.1. Pengumpulan Data 1. Metode Interview ( wawancara )
Metode  interview  ini  dilakukan  tanya jawab  dengan  staf  umum  dikecamatan Tawangmangu  berkaitan  tentang  nama villa dan jumlah villa yang ada dikecamatan Tawangmangu. 2. Observasi Penulis  mengunjungi  lokasi  villa  untuk mengambil  30  koordinat  lokasi  villa  dan meninjau langsung lokasi villa.
3. Studi Literatur Pada  metode  ini  penulis  mengumpulkan data  mengenai  pokok-pokok  bahasan yang berkaitan dengan penyusunan laporan yaitu mempelajari beberapa karya ilmiah, artikel dan referensi-referensi yang berkaitan dengan algoritma Floyd warshall,  Graf,  dan  lokasi  villa  di Kecamatan  Tawangmangu  yang  dapat digunakan sebagai acuan dalam penulisan.

## 3.2. Pengembangan Sistem
1. Analisa Sistem
Hasil  dari  pencarian  data  secara  primer diperoleh  data  lokasi  villa,  jarak,  dan jalan, yang akan digunakan untuk membuat aplikasi penentuan rute terpendek. Persoalan mencari rute terpendek di dalam graf merupakan salah satu  persoalan  optimasi.  Graf  yang digunakan dalam pencarian rute terpendek adalah graf berbobot (weighted graph), yaitu  graf  yang  setiap  sisinya diberikan suatu nilai atau bobot
2. Perancangan Sistem
a. Diagram Konteks Diagram  ini  menggambarkan  sistem penentuan rute terpendek secara garis besar dalam memperlihatkan masukan proses  dan  keluaran  dari  sistem  yang akan  dirancang  untuk  lokasi  villa  dan menggunakan algoritma Floyd warshall di Kecamatan Tawangmangu.
b. Hierarchy Input Proses Output HIPO digunakan untuk mempersiapkan penggambaran
diagram  alir  data  untuk  menuju  level- level  lebih  bawah,  dimana  memiliki jenjang yaitu top level, level 0,dan level 1.
c. Desain Diagram Alir Data
Diperlukannya
DFD (data flow diagram) yaitu suatu model logika data atau proses dibuat untuk
menggambarkan  darimana  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.
d. Perancangan Database
1. Entity Relationship Diagram (ERD) ERD untuk menggambarkan
hubungan  satu  tabel  dan  tabel lainnya.  Sehingga  dapat  terlihat batasan-batasannya  hubungan  dari satu  tabel  yang  dibuat.  Terdapat data jarak, data jalan, data kategori, dan sub kategori.
2. Strukur Tabel
Struktur tabel menggunakan struktur  tabel  didalam  database dimana  terdapat  data  admin,  data villa,  kategori,  data  jalan,  dan  data jarak.
e. Desain Interface
Desain  Interface  digunakan  untuk menggambarkan  struktur  tampilan website  berbasis  webgis  yang  akan diterapkan kedalam aplikasi .

## 3.3. Implementasi Sistem
Implementasi  dalam  pembuatan  aplikasi yaitu
menampilkan peta kecamatan tawangmangu yang meliputi jalan persimpangan Kecamtan Tawangmangu,
yang ditampilkan menggunakan Google Maps Api,  selanjutnya  perhitungan  mengunakan Algoritma Floyd Warshall.

## 3.4. Pengujian Sistem
1.  Blackbox Testing
Pada  pengujian  fungsional  sistem  ini menggunakan  teknik  pengujian Black Box Testing. Pengujian dilakukan
melihat  apakah  hasil  masukan  sistem benar  dengan  membandingkan  hasil keluaran sistem.
2.  Pengujian validitas
Pengujian  Validitas  dilakuan  dengan cara membandingkan perhitungan program  dengan  perhitungan  manual, sehingga dapat diketahui tingkat akurasi program yang kita buat. Pada pengujian validitas  hal  yang  harus  dilakukan menghitung secara manual dan perhitungan  sistem  memiliki  persamaan yang akurat.
3.  Uji Kelayakan Pengujian  kelayakan  pada  software pemilihan  rute  terdekat  ini  dilakukan dalam cara melakukan kuisioner kepada sekitar  8  orang  kemudian  hasilnya dihitung  apakah  memang  layak  untuk digunakan  dan  pengujian  google  maps apakah  sama  atau  berbeda  dengan google maps.

## IV.  HASIL DAN PEMBAHASAN
Algoritma
Floyd Warshall disini membandingkan semua kemungkinan lintasan pada  graf  untuk  setiap  sisi  dari  semua simpulnya. Hal ini dapat terjadi karena adanya perkiraan  pengambilan  keputusan  (pemilihan jalur  terpendek)  pada  setiap  tahap  antar  dua simpul,  hingga  perkiraan  tersebut  diketahui sebagai nilai optimal.
Dalam  contoh  kasus  ini  diambil  15  titik atau  node  dengan  Pertigaan  Pojok  (T01) sebagai  titik  awal  dan  Villa  Indra  Sari  (T10) sebagai  titik  tujuan,  beserta  jarak  antar  titik dengan satuan meter.

## Gambar 2 Contoh kasus Rute Terpendek
Keterangan :
T01 = Pertigaan Pojok T02 = Pertigaan Smp Amal Mulya T03 = Perempatan Karangkulon T04 = Pertigaan Grojokan T05 = Perempatan Toko Murah T06 = Perempatan Banjarsari
T07 = Perempatan Pukesmas T08 = Perempatan Lilik T09 = Pertigaan Anggi T10 = Villa Indra Sari T11 = Pertigaan River Hill T12 = Villa Wisma Bayangkara T13 = Villa Solomia T14 = Pertigaan Petasan T15 = Pertigaan Pion
Dari  Graf  yang  telah  diberikan  seperti Gambar  2,  yang  akan  dilewati  berdasarkan perhitungan  manual  yaitu  dengan  cara menjumlahkan jarak node yang terhubung dari titik awal ke titik tujuan pada setiap node yang dapat dilewati.
 T01-T02-T03-T04-T14-T15-T10
dengan panjang 1512m
 T01-T07-T08-T11-T12-T13-T14-T15-
T10 dengan panjang 2167m
 T01-T02-T03-T04-T05-T06-T09-T10 dengan panjang 1443m
Diperoleh hasil rute terpendek dari T01 ke T10  yaitu  :  T01-T02-T03-T04-T05-T06-T09- T10  dengan  total  jarak  1443m,  dimana melewati titik Pertigaan Pojok - Pertigaan Smp Amal  Mulya –  Pertigaan  Karangkulon  – Pertigaan Grojokan - Perempatan Toko Murah – Perempatan Banjarsari – Pertigaan Anggi – Villa Indra Sari
Berdasarkan  ilustrasi  contoh  graf  pada Gambar  2,  dimodelkan  ke  dalam  algoritma Floyd-Warshall  sehingga  diperoleh  matrik  W 0 seperti Tabel 2 :

## Tabel 2 Matrik W
0
Dari/ke  T01  T02  T03  T04  T05  T06  T07  T08  T09  T10  T11  T12  T13  T14  T15 T01 0 313 ∞ ∞
∞ ∞ 249 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ T02 313 0 329 ∞
∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ T03 ∞ 329 0 135 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ T04 ∞ ∞ 135 0 276 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 487 ∞
T05 ∞ ∞ ∞ 276 0 180 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
T06 ∞ ∞ ∞ ∞ 180 0
∞ ∞ 176 ∞ ∞ ∞ ∞ ∞ ∞ T07 249 ∞ ∞ ∞ ∞
∞ 0 123 ∞ ∞ ∞ ∞ ∞ ∞ ∞
T08 ∞ ∞ ∞ ∞
∞ ∞ 123 0 ∞ ∞ 535 ∞ ∞ ∞ ∞
T09
∞ ∞ ∞ ∞
∞ 176 ∞
∞ 0 34 ∞ ∞ ∞ ∞ ∞
T10 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 34 0 ∞ ∞ ∞ ∞ 164
T11
∞ ∞ ∞
∞ ∞
∞ ∞ 535 ∞ ∞ 0 72 ∞ ∞ ∞
T12
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ 72 0 822 ∞ ∞
T13 ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 822 0 118 ∞
T14
∞ ∞ ∞
487 ∞ ∞ ∞ ∞ ∞ ∞ ∞
∞ 118 0 84
T15
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 164 ∞ ∞ ∞ 84 0 Langkah selanjutnya melakukan
perhitungann  dengan  rumus  W[i,j]  =  min (W[i,j],W[i,k]+W[k,j]).  Dengan  dimulai  dari iterasi  K=T01  sampai  K=T15  berdasarkan Tabel 1.
1.  Iterasi K = T01 a.  Untuk  i  =  T01,  j  =  {T01,T02,T03,T04, T05,T06,T07,T08,T09,T10,T11,T12,T13,T1 4,T15}
•  W[T01,T01] = min (0,0 + 0) = 0
•  W[T01,T02] = min (313,0 + 313) = 313 •  W[T01,T03] = min (∞,0 + ∞) = ∞ •  W[T01,T04] = min (∞,0 + ∞) = ∞ •  W[T01,T05] = min (∞,0 + ∞) = ∞ •  W[T01,T06] = min (∞,0 + ∞) = ∞ •  W[T01,T07] = min (249,0 + 249) = 249 •  W[T01,T08] = min (∞,0 + ∞) = ∞ •  W[T01,T09] = min (∞,0 + ∞) = ∞
•  W[T01,T10] = min (∞,0 + ∞) = ∞ •  W[T01,T11] = min (∞,0 + ∞) = ∞ •  W[T01,T12] = min (∞,0 + ∞) = ∞ •  W[T01,T13] = min (∞,0 + ∞) = ∞ •  W[T01,T14] = min (∞,0 + ∞) = ∞ •  W[T01,T15] = min (∞,0 + ∞) = ∞
b.  Untuk  i  =  T02,  j  ={T01,T02,T03,T04, T05,T06,T07,T08,T09,T10,T11,T12,T13,T1 4,T15}
•  W[T02,T01] = min (∞,313 + 0) = 313
•  W[T02,T02] = min (0,313 + 313) = 0
•  W[T02,T03] = min (329,313 + ∞) = 329 •  W[T02,T04] = min (∞,313 + ∞) = ∞
•  W[T02,T05] = min (∞,313 + ∞) = ∞
•  W[T02,T06] = min (∞,313 + ∞) = ∞
•  W[T02,T07] = min (∞,313 + 249) = 562
•  W[T02,T08] = min (∞,313 + ∞) = ∞
•  W[T02,T09] = min (∞,313 + ∞) = ∞ •  W[T02,T10] = min (∞,313 + ∞) = ∞ •  W[T02,T11] = min (∞,313 + ∞) = ∞ •  W[T02,T12] = min (∞,313 + ∞) = ∞ •  W[T02,T13] = min (∞,313 + ∞) = ∞ •  W[T02,T14] = min (∞,313 + ∞) = ∞ •  W[T02,T15] = min (∞,313 + ∞) = ∞
c.  Untuk  i  =  T03,  j  ={T01,T02,T03,T04, T05,T06,T07,T08,T09,T10,T11,T12,T13,T1 4,T15} •  W[T03,T01] = min (∞,∞ + 0) = ∞ •  W[T03,T02] = min (329,∞ + 313) = 329 •  W[T03,T03] = min (0, ∞ + ∞) = 0
•  W[T03,T04] = min (135, ∞ + ∞) = 135 •  W[T03,T05] = min (∞,∞ + ∞) = ∞
•  W[T03,T06] = min (∞,∞ + ∞) = ∞ •  W[T03,T07] = min (∞,∞ + 249) = ∞
•  W[T03,T08] = min (∞,∞ + ∞) = ∞ •  W[T03,T09] = min (∞,∞ + ∞) = ∞ •  W[T03,T10] = min (∞,∞ + ∞) = ∞
•  W[T03,T11] = min (∞,∞ + ∞) = ∞ •  W[T03,T12] = min (∞,∞ + ∞) = ∞ •  W[T03,T13] = min (∞,∞ + ∞) = ∞
•  W[T03,T14] = min (∞,∞ + ∞) = ∞ •  W[T03,T15] = min (∞,∞ + ∞) = ∞
Perhitungan  terus  dilakukan  sampai  I  = k15,
j={T01,T02,T03,T04,T05,T06,T07,T08, T09,T10,T11,T12,T13,T14,T15}. Kemudian dilanjutkan sampai ke iterasi k = T15, dimana perhitungan  sama  dengan  iterasi  k  =  1. Hasil iterasi k =T15 berikut
Tabel 3 Matrik iterasi K=1=T15 Dari/ke  T01 T02 T03 T04 T05 T06 T07 T08 T09 T10 T11 T12 T13 T14 T15 T01 0 313 642 777 1053  1233 249 372 1409  1443 907 979 1382  1264  1348 T02 313 0 329 464 740 920 562 685 1096  1130  1220  1292  1069 951 1035 T03 642 329 0 135 411 591 891 1014 767 801 1549  1562 740 622 706 T04 777 464 135 0 276 456 1026  1149 632 666 1499  1427 605 487 571 T05 1053 740 411 276 0 180 1302  1425 356 390 1650  1578 756 638 554 T06 1233 920 591 456 180 0 1482  1781 176 210 1470  1398 576 458 374 T07 249 562 891 1026  1302  1482 0 123 1658  1692 658 730 1552  1513  1597 T08 372 685 1014  1149  1425  1781 123 0 1781  1795 535 607 1429  1547  1631 T09 1409  1096 767 632 356 176 1658  1781 0 34 1294  1222 400 282 198 T10 1443  1130 801 666 390 210 1692  1795 34 0 1260  1188 366 248 164 T11 907 1220  1549  1499  1650  1470 658 535 1294  1260 0 72 894 1012  1096 T12 979 1292  1562  1427  1578  1398 730 607 1222  1188 72 0 822 940 1024 T13 1382  1069 740 605 756 576 1552  1429 400 366 892 822 0 118 202 T14 1264 951 622 487 638 458 1513  1547 282 248 1012 940 118 0 84 T15 1348  1035 706 571 554 374 1597  1631 198 164 1096  1024 202 84 0
Berdasarkan    matrik  pada  Tabel  3  akan dicari  rute  terpendek  dari  T01  ke  T10 berdasarkan  perhitungan  algoritma  Floyd Warshall adalah T01 – T02 – T03 – T04 – T05 – T06 – T09 – T10 dengan jarak 1443 meter.
Perancangan
sistem dilakukan menggunakan  Diagram  Konteks,  HIPO,  DFD dan  menggunakan  interface  Bootstrap  serta XAMPP Web Server.
Diagram  konteks  secara  garis  besar menggambarkan sistem penentuan rute terpendek
dengan memperlihantkan
masukkan,  proses,  dan  keluaran  dari  sistem yang  akan  dirancang  untuk  penentuan  rute terpendek lokasi villa di Kecamatan Tawangmangu.  Adapun  Diagram  Konteks dapat ditunjukkan pada Gambar 3.

## Gambar 3 Diagram Konteks
Hierarcy  Input  Process  Output (HIPO) digunakan  untuk  teknik  pendokumentasian program yang dapat digunakan untuk mengkomunikasikan spesifikasi sistem kepada para level –level lebih bawah lagi. Setiap modul
HIPO  digambarkan  oleh  fungsi  utamanya. Diagram HIPO dapat ditunjukkan pada Gambar 4.

## Gambar 4 Diagram HIPO
Data  Flow  Diagram atau  DFD  merupakan diagram diagram aliran data dimana menjelaskan masing-masing bagian dan fungsinya dalam menerima dan mengirim data. Data  Flow  Diagram  dapat  ditunjukkan  pada Gambar 5.

## Gambar 5 Data Flow Diagram
Entity  Relationship  Diagram    (ERD) digunakan  untuk  menggambarkan  keterkaitan data  antar  field  dan  tabel  di  dalam  database. Database  yang  digunakan  adalah  database
MySQL. Adapun diagram ERD dapat ditunjukkan pada Gambar 6

## Gambar 6 ERD Database
Interface web digunakan untuk memudahkan  pengelolaan  dan  menampilkan hasil  ke  dalam  bentuk  tampilan  yang  mudah dipahami  serta  dapat  digunakan  oleh  user umum.  Interface  web  dapat  ditunjukkan  pada Gambar 7.

## Gambar 7 Interface Web
Dalam  pengujian  yang  dapat  diuraikan pada  Tabel  4  yang  telah  dilakukan  dan  hasil perhitungan  manual  dan  perhitungan  program pada Gambar 8 adalah sama.
Tabel 4. Pengujian
Rute Manual Program Hasil Rute Alternatif Jarak Rute Jarak T01-T02-T03- T04-T14-T15- 1512 1443 Hasil Sama
Rute Manual Program Hasil Rute Alternatif Jarak Rute Jarak T01 – T10 T10 T01- T02- T03- T04- T05- T06- T09- T10
T01-T02-T03- T04-T05-T06- T09-T10 1443 T01-T07-T08- T11-T12-T13- T14-T15-T10 2167
Penghitungan  manual  ini  merupakan penghitungan  yang  dilakukan  secara offline . Dimana diukur dilapangan dengan menggunakan kendaraan
bermotor.
Sedangkan penghitungan program, berdasarkan jumlah jarak antar titik yang dilalui mulai  dari  awal  sampai  tujuan.  Jarak  diambil berdasarkan koordinat di masing-masing titik.

## Gambar 8 Hasil perhitungan program
Pengujian  kelayakan  digunakan  untuk mengukur  tingkat  kelayakan  penggunaan aplikasi  untuk  dioperasikan.  Pengujian  ini dilakukan dengan cara membandingkan dengan Google Maps yang sudah di lakukan.
Tabel 5 pengujian dengan Google Maps Lokasi Asal Lokasi Tujuan Perbandingan Program Dengan Google Map Perempatan Balekambang Villa Subasa Berbeda Dengan Program Villa Tanaman Villa Ngrotosari Berbeda Dengan Program Perempatan Banjarsari Villa Stroberry Berbeda Dengan Program Pertigaan Smp Amal Mulya Villa Bayangkara Berbeda Dengan Program Villa Stroberry Villa Indra Sari Berbeda Dengan Program
Lokasi Asal Lokasi Tujuan Perbandingan Program Dengan Google Map Perempatan Bu Ugi Villa Solomia Berbeda Dengan Program Perempatan Londo Villa Sar Berbeda Dengan Program Perempatan Bener Villa 96 Berbeda Dengan Program Grojokan Villa Panti Asri Berbeda Dengan Program Pertigaan Pion Villa BK Berbeda Dengan Program Pertigaan Petasan Villa Murnia Husein Berbeda Dengan Program Perempatan Pukesmas Villa Masikama Berbeda Dengan Program Pertigaan Pojok Villa Sari Asih Berbeda Dengan Program Pertigaan Jembatan Villa Harjuna Berbeda Dengan Program Pertigaan Naga Villa Tanaman Berbeda Dengan Program Grojokan Sewu Villa Hanif Berbeda Dengan Program Perempatan Wc Villa Abas Berbeda Dengan Program Perempatan Kampung baru Villa Marais Berbeda Dengan Program Pertigaan Anggi Villa Maya Berbeda Dengan Program Perempatan Sari Villa Sritek Berbeda Dengan Program Pwertigaan River Hill Villa Dahlia Berbeda Dengan Program Pertigaan Butransno Villa Bunda Hana Berbeda Dengan Program Perempatan lilik Villa Putih Berbeda Dengan Program Pertigaan Pancot Villa Bunda Novi Berbeda Dengan Program Pertigaan Oro- oro Villa Je Sama Dengan Program Perempatan Matisih Villa Handoyo Sama Dengan Program Pasar Tawangmangu Villa Vtec Sama Dengan Program Pertigaan Hi Villa Titi Sari Sama Dengan Program Pertigaan Sakaw Villa Sartika Sama Dengan Program Pertigaan Sekipan Villa Wahyu Kinanti Sama Dengan Program Berdasarkan percobaan
pengujian kelayakan  menggunakan  Google  Maps  pada Tabel  5  menunjukan  hasil  yang  berbeda mendapatkan persentase perbedaan 80% dari 30 jalur percobaan dengan Google Maps.
Perbedaan  ini  dikarenakan  Google  Maps membaca  kondisi  lalu  lintas  jalan,  dan membandingkan referensi jalan lain. Selain itu, penggunaan Floyd-Warshall ini hanya mengacu pada jalan yang dapat dilalui dengan kendaraan roda 2 atau lebih.
Pengujian kelayakan juga dilakukan untuk mengukur  kepuasan  pengguna  aplikasi.  Mulai dari kemudahan menggunakan aplikasi, lokasi mudah  digunakan  untuk  menetukan  titik  awal dan  tujuan,  memudahkan  pencarian  Villa sampai  dengan  tampilan  interface  yang menarik.
Dari  8  (delapan)  responden  yang  diambil secara acak, menunjukkan persentase kelayakan  sebesar  88,75%  diukur  dengan skala linkert 5 (lima) untuk masing-masing lima pernyataan.

## V.  PENUTUP
Berdasarkan dari analisa dan implementasi sistem penentuan rute terpendek lokasi villa di Kecamatan  Tawangmangu  yang  dilakukan, maka  dapat  diambil  beberapa  kesimpulan yaitu  dapat  memudahkan  pengguna  untuk menentukan  lokasi  villa  dan  rute  terpendek yang menggunakan perhitungan Floyd warshall  dari  lokasi  asal  sampai  lokasi  tujuan villa dan informasi berkaitan dengan villa lebih rinci.
Pengujian  kelayakan  dengan  responden menunjukan hasil persentasi kelayakan sebesar  88,75%  yang  menunjukkan  bahwa aplikasi  yang  dibuat  sangat  layak  digunakan oleh  pengguna,  dan  Pengujian  kelayakan dengan  Google  Map  menunjukan  bahwa program dengan Google Maps ada perbedaan 80% dari pengujian jalur berbeda.
Penelitian lebih lanjut dapat dikembangkan dengan penggabungan algoritma yang lainnya serta  dapat  diimplementasikan  ke  dalam aplikasi berbasis Android.

## DAFTAR PUSTAKA
[1] E. Budiyanto, S. Pd, and M. Si, “Sistem Informasi  Geografis  dengan  Quantum GIS,” Andi, Yogyakarta , 2016.
[2] D.  Nugroho  and  E.  Purwanto,  “Marker Berbeda-Beda  untuk  Sistem  Informasi Geografis  Menggunakan  PHP,  Google Map  API  dan  Akses  Langsung  Ke MySql,” DutaCom  J. ,  vol.  13,  no.  1,  pp.
71 –82, 2017.
[3] W. O. A. P. Wulandari, B. Pramono, and
L.  M.  Tajidun,  “Aplikasi  Pencarian  Rute Terpendek  Apotek  Di  Kota  Kendari Menggunakan Algoritma Floyd- Warshall,” semanTIK ,  vol.  3,  no.  1, 2017.
[4] D.  B.  Prasetyo,  “Sistem  Informasi
Geografis  Berbasis  Google  Maps  API untuk  Pemetaan  Profil  Kriminalitas  Tipe Konvensional di
Wilayah Hukum
Polresta  Yogyakarta,” J.  Tek.  Inform.
STMIK AMIKOM Yogyakarta , 2014. [5] H.  Sulastri,  H.  Mubarok,  and  A.  Heykal, “Sistem Pendukung Keputusan Penentuan  Rute  Terbaik  Menuju  Posko Pendakian Gunung Ciremai Menggunakan Algoritma Floyd Warshall Dan  Weighted  Product,”  in SNIA (Seminar  Nasional  Informatika  dan
Aplikasinya) , 2019, vol. 4, pp. B17-22.
[6] F.  W.  Ningrum,  “Penerapan  Algoritma
Floyd-Warshall dalam Menentukan Rute Terpendek  pada  Pemodelan  Jaringan Pariwisata di Kota Semarang.” Universitas Negeri Semarang, 2016. [7] N.  K.  D.  A.  Jayanti,  “Penggunaan Algoritma Floyd Warshall Dalam Masalah Jalur Terpendek Pada
Penentuan  Tata  Letak  Parkir,”  in
Seminar  Nasional  Informatika  (SNIf) , 2017, vol. 1, no. 1, pp. 75 –81.
[8] J.  Kepner  and  J.  Gilbert, Graph algorithms  in  the  language  of  linear algebra . SIAM, 2011.