## PENERAPAN ALGORITMA FLOYD WARSHALL UNTUK MENENTUKAN JALUR TERPENDEK DALAM PENGIRIMAN BARANG

## Ahyar Rivai Hasibuan
Mahasiswa Teknik Informatika  STMIK  Budi Darma Medan Jl. Sisingamangaraja Np. 338 Simpang Limun Medan

## ABSTRAK
Algoritma  Floyd  Warshall  adalah  salah  satu  yang  sederhana  dan  mudah  inplementasinya.  algoritma  Floyd  Warshall memulai iterasi dari titik awalnya kemudian memperpanjang path dengan mengevaluasi titik demi titik hingga mencapai titik tujuan  denag  jumlah  bobot  yang  seminimum  mungkin.  Pada  skiripsi  ini,  penulis  melakukan  suatu  penerapan  algoritma Warshal  pada  penentuan  jalur  terpendek  dengan  menggunakan  graf  berbobot  untuk  menghasilkan  jalur  terpendek  yan g dilalui dalam proses pengiriman barang. Perhitungan akan diimplementasikan dengan algoritma Floyd Warshall   dengan menghitung  bobot  terkecil  dari  titik  awal  ke  titik  tujuan.  Hasil  perhitungan  akan  diterapkan  kedalam  perangkat  lunak aplikasi dengan mengunakan visual studio 2010. Perancangan sisitem dilakukan dengan beberapa tahapan, yaitu pembuatan use case diagram, Activity diagram dan rancangan antar muka.

## Kata kunci : algoritma floyd warshall, jalur terpendek

## I. PENDAHULUAN
Komunikasi  memiliki  peran  pada  setiap perusahaan  dalam  menyikapi  persaingan  yang  akan menjadi semakin ketat dengan perusahaan-perusahaan lain dari seluruh dunia. Persaingan  yang  begitu keras memaksa  pengusaha  agar  lebih  proaktif  dalam memasarkan  dan  mempertahankan  produk  yang ditawarkan  pada  konsumen,  agar  konsumen  tetap bertahan  mengkonsumsi  produk  yang  ditawarkan. Untuk  itu,    setiap  perusahaan  dituntut  untuk  tetap mampu  bertahan  dan  berusaha  meningkatkan  segala kemampuannya dalam rangka meningkatkan pelayanan untuk merebut pangsa pasar  yang  semakin kritis.  Algoritma  dapat  didefinisikan  sebagai  urutan langkah-langkah  logis  dan  sistematis  dalam  mencari suatu  solusi  dari  suatu  permasalahan  yang  ada. Langkah-langkah  dalam  memecahkan  masalah  bisa dilakukan  dalam  berbagai  cara  dengan  karaktristik yang  berbeda-beda  dari  masing-masing  langkah. Tiap-tiap algoritma tersebut memiliki cara kerja yang berbeda-beda  dalam  mennetukan  solusi  yang  paling optimal.
Permasalahan utama pencarian jalur terpendek tentu  saja  mencari  jalur  atau  rute  terpendek  yang memungkinkan.  Namun  untuk  implementasikan, persoalan  ini  dapat  dikembangkan  lebih  luas  lagi diantaranya  untuk  mencari  biaya  minimum  dan  jalur perjalanan  yang  terpendek.  Intinya  adalah  mencari solusi  yang  paling  efektif  yang  dapat  diterapkan dalam persoalan yang dihadapi.

## II. TEORITIS

## A. Penerapan
Menurut  Nurdin  Usman  dalam  bukunya  yang berjudul  konteks  implementasi  berbasis  kurikulum mengemukakan  pendapatnya  mengenai  implementasi atau  penerapan  sebagai  berikut  :  “  Implementasi adalah  bermuara  pada  aktivitas,  aksi,  tindakan  atau adanya mekanisme suatu sistem. Implementasi bukan sekedar  aktivitas,  tetapi  suatu  kegiataan  yang terencana  untuk  mencapai  tujuan  kegiataan  (Usman, 2002).

## B. Algoritma Floyd Warshall
Algoritma  Floyd  Warshall  adalah  matriks  hubung graf  berarah  berlabel,  dan  keluarannya  adalah path terpendek  dari  semua  titik  ke  semau  titik.  Dalam usaha untuk mencari path terpendek, algoritma Floyd Warshall memulai iterasi dari titik awalnya kemudian memperpanjang path dengan mengevaluasi titik demi titik  hingga  mencapai  tujuan  dengan  jumlah  bobot yang seminimum mungkin (Siang Jong Jek, 2009).
Algoritma  Floyd  Warshall  adalah  salah  satu varian  dari  pemrograman  dinamis,  metode  untuk memecahkan masalah pencarian rute terpendek (sama seperti  Algoritma  Floyd  Warshall).  Metode    ini melakukan  pemecahan  masalah  dengan  memandang solusi  yang  akan  diperoleh  sebagai  suatu  keputusan yang saling terkait. Maksudnya solusi-solusi dibentuk dari  solusi  yang  berasal  dari  tahap  sebelumnya  dan ada  kemungkinan  solusi  lebih  dari  satu.  Algoritma Floyd Warshall merupakan algoritma yang mengambil  jarak  minimal  dari  suatu  titik  ketitik lainnya.  Pada  algoritma  ini  menerapkan  suatu algoritma dinamis yang menyebabkan akan mengambil jarak lintasan terpendek secara benar.
Algoritma  Floyd  Warshall  ini  juga  bisa diterapkan  pada  sebuah  aplikasi  pencari  rute  jalan yang  terdekat  dari  suatu  daerah  ke  daerah  lainnya dengan  metode  ini  hasil  yang  didapat  bisa  lebih optimal  namun  memerlukan resource yang  cukup besar jika dipakai untuk mencari komplek.
Algoritma Floyd Warshall  memiliki input graf berarah  dan  berbobot  ( V , E ),  yang  berupa  daftar  titik ( node/vertexV )  dan  daftar  sisi  ( edgeE ).  Jumlah  bobot sisi-sisi pada sebuah jalur adalah bobot jalur tersebut. Sisi  pada E diperbolehkan  memiliki  bobot  negatif, akan  tetapi  tidak  diperbolehkan  bagi  graf  ini  untuk memiliki  siklus  dengan  bobot  negatif.  Algoritma  ini menghitung  bobot  terkecil  dari  semua  jalur  yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik.
Algoritma  Floyd  Warshall  ditemukan  oleh Warshall  untuk  mencari path terpendek  merupakan algoritma yang sederhana dan mudah implementasikannya.  Algoritma  Floyd  Warshall adalah  matriks  hubung  graf  berarah  berlabel,  dan
keluarannya  adalah  p ath terpendek  dari  semua  titik kesemua titik.
Dalam usaha mencari jalur terpendek, algoritma Warshall memulai iterasi dari titik awalnya kemudian memperpanjang path dengan mengevaluasi titik  demi  titik  hingga  mencapai  titik  tujuan  dengan jumlah bobot yang seminimum mungkin. (Siang Jong Jek, 2009)

## C. Shortest Path Problem
Jalur pendek adalah suatu jaringan pengarahan perjalanan  dimana  seseorang  pengarah  jalan  ingin menentukan  jalur  terpendek  antara  dua  perusahaan, berdasarkan  beberapa  jalur  alternatif  yang  tersedia, dimana titik tujuan hanya satu.
Data kuantitaf dalam penelitian ini adalah hasil pengukuran  jarak  jalur-jalur  dari  titik  evakuasi menuju  zona  aman.  Data  kualitatif  dalam  penelitian ini berupa peta evakuasi Tsunami yang diperolah dari Badan  penaggulangan  bencana  daerah  (BPBD) Propinsi  Bali.  Teknik  pengumpulan  data  yang digunakan  dalam  penelitian  ini  meliputi,  observasi, dokumentasi, literatur, dan wawancara. Variabel yang digunakan  dalam  penelitian  ini  adalah  jarak  dari setiap  jalur-jalur  yang  mungkin  dapat  dilalui  dari pantai-pantai  yang  berada  dikelurahan  Sanur  yaitu Pantai Segara ( V 3 ), Pantai Shindu ( V 8 ), Pantai Karang ( V 19 ),  Pantai  Duyung  ( V 20 ),  Pantai  Semawang  ( V 26 ), Pantai  Cemara  ( V 29 ),  untuk  menuju  zona  aman  di Puskesmas  III  Denpasar  Selatan  ( V 4 ),  dan  SMK Negeri 3 Denpasar ( V 33 ).
Gambar 1 : Representasi Peta Kelurahan Sanur kedalam bentuk graf (Satuan Kilometer)
(Sumber  :  Ajeng  Fitrah  Sani,  Ni  Ketut,  Tastrawati dan  I  Made  Eka  Dwipayana,  Algoritma  Floyd Warshall  Untuk  Menentukan  Jalur  Terpendek Evakuasi Tsunami Dikelurahan Sanur, 2013)
Hasil  Transformasi  Graf  direfresentasikan kedalam  bentuk  matriks  ketetanggaan  dan  diproses dengan  menggunakan  Algoritma  Floyd  Warshall. Algritma  Floyd  Warshall  untuk  mencari  path terpendek  (Siang,  4  :301)  Dimisalkan  W 0 adalah
matriks ketetanggaan awal Graf berarah berbobot. W* adalah  matriks  ketetanggaan  berbobot  terpendek dengan  W ij sama  dengan  path  terpendek  dari  titik  V i ke V j . 1) W = W 0
2) Untuk k = 1 hingga n, lakukan : Untuk i = 1 hingga n, lakukan :
Untuk j = 1 hingga n , lakukan : 3) Jika W [i j] > W [i, k] + W [k, j] maka Tukar W [i, j] dengan W [i, k] + W [k, j]
4) W* = W
Untuk itrasi k =1
Pada  setiap  elemen  matriks  W  dilakukan pengecekan apakah W [i j] > W [i, k] + W [k, j]. Jika ya,  maka  ganti  W  [i,  j]  dengan  W  [i,  k]  +  W  [k,  j]. Contoh:
W[1, 2] = 0,1, sedangkan W [1, 1] + W [1, 2] = ∞ + 0,1 = ∞ karena W [1, 2] i > W [1, 1] + W [1, 2] maka bobot W [1, 2] tidak diubah.
W [2, 4] = ∞, sedangkan W [2, 1] + W [1, 4] = 0,1 + 0,4 = 0,5.
Karena  W [2, 4] > [2, 1] +  W [1, 4],  maka  bobot W [2, 4] di ubah menjadi 0,5.
Berarti,  ada  path  dari  V 2 ke  V 4 melalui  V 1 yang mempunyai  bobot  lebih  kecil  yaitu  path  V 2 V 1 V 4 dengan  jumlah  bobot  0,5.  Kemudian  dengan  cara yang sama, harga W [i, j] dihitung untuk setiap i dan j.  Penghitungan  iterasi  dilakukan  hingga  iterasi  k  = 37.
Untuk  mengetahui  jalur  terpendek  dari  setiap titik  evakuasi  menuju  zona  aman  maka  perhatikan perubahan bobot dari setiap iterasi. Misalnya dari titik evakuasi  Pantai  Segara  (V 3 )  menuju  zona  aman evakuasi  yang  berada  di  Puskesmas  III  Denpasar Selatan (V4):
Pada  iterasi  k  =  37,  jarak  terpendek  dari  (V 3 ) ke    (V 4 )  sebesar  0,9  Km.  Hal  ini  berarti  jalur-jalur sejauh  0,9  Km  untuk  menuju  zona  aman  evakuasi  di (V 4 ).  Lakukan  pengecekan  dari  (V 3 )  ke  (V 4 )  pada setiap k untuk mengetahui perubahan setiap bobotnya. (V 3 ) ke (V 4 ) memiliki  bobot 0,9 Km pada  saat k  = 2 hal ini berarti terdapat jalur terpendek dar (V 3 ) ke (V 4 ) melalui  (V 2 ).  Kemudian  perhatikan  Graf  untuk mengetahui  (V 3 )          (V 2 )            (V 4 )  telah  terhubung. Verteks  (V 3 )  ke  (V 2 )  telah  terhubung,  sedangkan verteks (V 2 ) ke (V 4 ) telah terhubung. Ini berarti belum diketahui  verteks  penghubung    dari  verteks  (V 2 )  ke (V 4 ). Pada iterasi k = 37, jarak terpendek dari (V 2 ) ke (V 4 )  sebesar  0,5  Km.  Lakukan  pengecekan  dari  (V 2 ) ke  (V 4 )  pada  setiap  k  untuk  mengetahui  perubahan setiap  bobotnya.  (V 2 )  ke  (V 4 )memiliki  bobot  0,5 Km pada saat k =1 hal ini berarti terdapat jalur terpendek dari  (V 2 )  ke  (V 4 )  melalui  (V 1 ).  Perhatikan  Graf kembali untuk mengetahui (V 2 )     (V 1 )     (V 4 ) telah terhubung.  (V 2 ),  (V 1 ),(V 4 )  telah  terhubung  sehingga pengecekan  selesai.  Diperoleh  jalur  terpendek  dari (V 2 ) ke (V 4 ) yaitu (V 3 )     (V 2 )     (V 1 )     (V 4 ) sejauh 0,9 Km.
Tabel  1. Hasil pemrosesan dengan menggunakan Algoritma Floyd Warshall dari     Titik-titik Evakuasi M menuju SMK Negeri 3 Denpasar (V 33 ).
Puskesmas III Segara (V3) V 3 , V 2 , V 1 , V 4 0.9 Denpasar Selatan Shindu (V8) V 8 ,V 7 , V 6 , V 5 ,V 4 0.74 Karang (V19) V 19 ,V 35 ,V 15 ,V 10 ,V 7 ,V 6 ,V 5 ,V 4 1.94 Duyung(V20) V 20 ,V 36 ,V 22 ,V 21 ,V 31 ,V 30 ,V 4 3 Semawang(V26) V 26 ,V 25 ,V 24 ,V 23 ,V 22 ,V 21 ,V 31 , V 30 ,V 4 3.1 Cemara (V29) V 29 ,V 37 ,V 25 ,V 24 ,V 23 ,V 22 ,V 21 , V 31 ,V 30 ,V 4 , 3.5
Tabel.2 Hasil Pemrosesan dengan Menggunakan Algoritma Floyd Warshall dari Titik-titik Evakuasi M menuju SMK Negeri 3 Denpasar (V 33 ). SMK Negeri 3 Denpasar (V33) Segara (V3) V 3 , V 2 , V 1 , V 4 ,V 30 ,V 32 ,V 33 3 Shindu (V8) V 8 ,V 7 , V 6 , V 5 ,V 4 ,V 30 ,V 32 , V 33 2.84 Karang (V19) V 19 ,V 35 ,V 18 ,V 17 ,V 16 ,V 21 , V 31 ,V 33 2.6 Duyung(V20) V 20 ,V 36 ,V 22 ,V 21 ,V 31 ,V 33 2 Semawang(V26) V 26 ,V 25 ,V 24 ,V 23 ,V 22 ,V 21 , V 31 , V 33 1.8 Cemara (V29) V 29 ,V 37 ,V 28 ,V 27 ,V 33 1.9 Kesimpulan 1) Telah  berhasil  dibentuk  jalur-jalur  terpendek evakuasi Tsunami di Sanur dengan menggunakan Algoritma Floyd Warshall.
2) Dapat disimpulkan titik-titik awal evakuasi yang berada  di  Pantai  Segara,  Shindu,  dan  Karang memilki  jarak  evakuasi  lebih  dekat  apabila menuju Puskesmas III Denpasar Selatan dibandingkan  ke  zona  aman  evakuasi  yang berada  di  SMK  Negeri  3  Denpasar  sebaliknya, titik-titik  awal  evakuasi  yang  berada  di  pantai Duyung,  Semawang,  Cemara  memiliki  jarak evakuasi terdekat di SMK Negeri 3 Denpasar.

## III. ANALISA DAN PEMBAHASAN
Pencarian  rute  terpendek  adalah  suatu pencarian  rute dari suatu jalur ke jalur lainya  untuk meminimaliasi  jarak  pada  suatu  lintasan  tertentu yang  saling  berhubungan.    Persoalan  lintasan terpendek  ini  sering  dilakukan  didalam  graf  dan merupakan  salah  satu  masalah  optimasi.  Dalam pencarian jalur terpendek dengan menggunakan graf berbobot. Asumsi pada penentuan jalur terpendek ini bahwa  setiap  bobot  bernilai  positip.  Lintasan terpendek sering dipakai untuk pencarian jarak antar suatu  kota  dalam  kasus  pengiriman  barang  agar menghasilkan jarak yang minimum.

## Penerapan  Jalur  Terpendek  Dengan  Algoritma
Floyd Warshall
Algoritma Warshall adalah algoritma penentuan  rute  tependek  dengan  menggunakan  graf berarah  berbobot.  Dalam  pencarian  ruteterpendek algoritma  Warshall  memulai  iterasinya  dari  titik awalnya  kemudian  memperpanjang path dengan mengepaluasi  titik  demi  titik  hinga  mendapatkan rute  terpendek.  Berikut  ini  adalah  kasus  penentuan jalur  terpendek  dengan  menggunakan  algoritma Warshal.  Berikut  ini  merupakan  contoh  penentuan
jalur  terpendek  dengan  menggunakan  Algoritma Warshall.
Gambar 2 : Graf Penentuan Jalur Terpendek
Tabel 3:  Matriks
V1  V2  V3  V4  V5 V 1 ∞ 6 ∞ 8 ∞ V 2 ∞ ∞ ∞ ∞ 12 V 3 7 ∞ ∞ ∞ 15 V 4 ∞ 4 4 ∞ ∞ V 5 ∞ ∞ ∞ 10 ∞
RUMUS =W [I, J ] > W [I, K ] + W [K, J]
V1  V2  V3  V4  V5 V 1 19 6 12 8 18 V 2 33 26 26 22 12 V 3 7 13 19 15 15 V 4 17 4 4 17 16 V 5 21 14 14 10 26
Berdasarkan  data  diatas,  dapat  dihitung  jalur terpendek  dengan  mencari  jarak  antar  jalur-jalur tersebut.  Dan  hasil  dari  data  diatas  dapat  diketahui jalur  terpendek  dari  A  (pengiriman  barang)  menuju G  (tujuan  pengiriman  barang)  yaitu  jarak  melalui jalur V 1 53 KM
12 V1 V3 V4 V5 V2 6 8 15 4 10 4 7 Jarak (Km)

## IV. IMPLEMENTASI
Untuk  menjalankan  program  pencarian  jalur terpendek  dengan  menggunakan  algoritma  Floyd Warshall  Harus  terlebih  dahulu  memepersiapkan kebutuhan  agar  dapat  diimplementasikan  pada aplikasi yang dirancang nantinya.

## Menu Tampilan
Gambar 3 : Menu Utama
Berikut ini adalah pseudocode dari algoritma Floyd Warshall untuk menentukan jalur terpendek. N=node/titik I=titik awal J=titik ahir K=iterasi function fw(int[1..n,1..n] graph) { // Inisialisasi var int[1..n,1..n] jarak := graph var int[1..n,1..n] sebelum for i from 1 to n for j from 1 to n if jarak[i,j] < Tak hingga sebelum[i,j] := i // Perulangan utama pada algoritma for k from 1 to n for i from 1 to n for j from 1 to n if jarak[i,j] > jarak[i,k] + jarak[k,j] jarak[i,j] = jarak[i,k] + jarak[k,j] sebelum[i,j] = sebelum[k,j] return jarak }
Tampilan Data Barang
Gambar 4 : Form Data Barang
TampilanRute
Gambar 5 : Form Rute
TampilanProfil
Gambar 6 : Profil

## V. KESIMPULAN
Setelah menerapkan kedalam perangkat lunak penentuan  jalur  terpendek  menggunakan  algoritma Floyd  Warshall  maka  dapat  diambil  kesimpulan bahwa :
1. Perancangan  aplikasi  data  penentuan  jalur terpendek  merupakan  salah  satu  cara  kerja dalam  pengantaran  barang  yang  dapat menganalisis  data  rute  terpendek    dengan menggunakan algoritma Floyd Warshall.
2. Perangkat lunak ini dapat dijadikan sebagai aplikasi  untuk  mendapatkan  hasil  rute terpendek.
3. Sistem  yang  penulis  rancang  sudah  bisa dijalankan kedalam Windows 7.

## VI. DAFTAR PUSTAKA
1. Usman. (2002). Konteks Implementasi Berbasis Kurikulum . Jakarta. Penerbit Andi 2. Munir.  Rinaldi.(2010). Matematika  Diskrit .  Bandung. Penerbit Informatika 3. Munir.  Rinaldi.  (2007). Algoritma  Dan  Pemerograman Dalam  Bahasa  Pascal  Dan  C .  Bandung.Penerbit Informatika. 4. Siang.  Jong.  Jek  (2009). Matematika  Diskrit  Dan Aplikasinya  Pada  Ilmu  Komputer Yogyakarta.  Penerbit Andi 5. Peranginangin.  Kasiman.  (2006). Aplikasi  WEB  dengan PHP dan MySQL. Yogyakarta. Penerbit Andi. 6. Ajeng  Fitrah  Sani,  Ni  Ketut,  Tastrawati  dan  I  Made  Eka Dwipayana(2003), Algoritma  Floyd  Warshall  Untuk Menentukan  Jalur  Terpendek  Evakuasi  Tsunami Dikelurahan Sanur, 3 . 7. www.Wikipedia . mei 5. (2003) .23.33 8. Ani.Moh.Sjuk.  (2008). Struktur  Data  Dan  C.C++. Penerbit Mitra Wacana Media . Jakarta