Algoritma Floyd Warshall Pencarian Rute Terdekat Dengan Php
04-April-2017 - Publish Admin

Algoritma Floyd Warshall adalah suatu metode yang paling umum untuk digunakan dalam mencari rute terpendek. Algoritma ini memiliki input dari grap yang sangat berarah dan berbobot, yang berupa titik node dari setiap rute yang bisa dilewati.

Algoritma Floyd Warshall sangat cocok digunakan karena hasil keluaranya yang dapat dibilang sangat akurat dan tepat sehingga dapat memberikan solusi dalam pencarian rute terdekat dari titik Star ke titik yang akan ditujuh.

Algoritma ini sangat cocok jika di implementasikan ke perusahaan yang bergerak dibidang transportasi seperti perusahaan Taxi, jasa kurir,Gojek dan masih banyak lagi yang lain.

Mekanisme algoritma Floyd Warshall

Langkah awal yang harus dilakukan untuk menentukan shortest path dengan menggunakan algoritma Floyd Warshal adalah :

• merepresentasikan suatu graph sebagai suatu matriks bobot. Dimana bobot untuk masing-masing edge adalah:
      wij = 0 jika i = j,
           = w(i,j) jika i ≠ j dan (i,j) Є E
           = ∞ jika i ≠ j dan (i,j) not(E)
• Format output berupa matrix n x n berjarak D = [dij] dimana dij adalah jarak dari vertex i ke j.

Langkah Kedua yaitu:

• melakukan dekomposisi Floyd Warshall. Urutannya adalah sebagai berikut:
  1. dij(k) merupakan panjang dari shortest path dari i ke j sehingga semua vertex intermediate yang terdapat pada path (jika ada) terkumpul pada (1, 2, …, k}.
  2. dij(0) dikumpulkan pada wij, dimana berarti kondisi tidak ada vertex intermediate
  3. D(k) menjadi matrix n x n [dij(k)]
  4. Tentukan dij(n) sebagai jarak dari i ke j. Jadi, yang dilakukan selanjutnya adalah menghitung D(n) -> D(n) beranggotakan elemen-elemen dij(n)
  5. Hitung D(k) untuk k = 0, 1, …, n.

Langkah Ketiga Yaitu

• menentukan struktur shortest path. Dalam hal ini, harus dilakukan dua pengamatan terlebih dahulu sebelum melangkah lebih jauh, yaitu:
  1. Sebuah shortest path tidak memuat vertex yang sama sebanyak 2 kali. Sebuah path yang memuat vertex 2 kali merupakan cycle.
  2. Untuk sebuah shortest path dari i ke j dengan beberapa vertex intermediate pada path dipilih dari kumpulan {1, 2, …, k), dengan 2 kemungkinan:
     1. k bukan vertex pada path, path terpendek mempunyai panjang dij^{(k – 1)}
     2. k adalah vertex pada path, path terpendek mempunyai panjang dik^{(k – 1)} + dkj^{(k – 1)}
  3. Setelah melakukan pengamatan di atas, kemudian dilakukan penentuan shortest path dari i ke j yang memuat vertex k.
  4. Shortest path tersebut memuat sebuah subpath dari i ke k dan sebuah subpath dari k ke j.

     

  5. Setiap subpath hanya dapat memuat vertex intermediate pada {1, …, k-1} dan sedapat mungkin haruslah paling pendek, beri nama panjangnya dik^{(k – 1)} dan dkj^{(k – 1)}. Sehingga path mempunyai panjang dik^{(k – 1)} + dkj^{(k – 1)}
  6. Dengan menggabungkan dua persamaan tersebut, maka didapat :
     - dij^(k) = min { dij^{(k – 1)}, dik^{(k – 1)} + dkj^{(k – 1)}}

Langkah Keepat yaitu:

• melakukan iterasi. Dimulai dari iterasi ke-0 sampai dengan n
• Perhitungan yang dilakukan adalah:
  1. Menentukan D(0) ( iterasi ke-0 )= [wij], merupakan matrix bobot
  2. Menentukan D(k) dengan menggunakan dij^(k) = min { dij^{(k – 1)}, dik^{(k – 1)} + dkj^{(k – 1)}}, untuk k = 1, …, n.
     1. k bukan vertex pada path, path terpendek mempunyai panjang dij^{(k – 1)}
     2. k adalah vertex pada path, path terpendek mempunyai panjang dik^{(k – 1)} + dkj^{(k – 1)} Dimana n adalah jumlah verteks
• Hasil akhir dari algoritma Floyd Warshall adalah matriks untuk iterasi ke-n. Dari matriks ke-n ini, dapat dilihat shortest path untuk setiap vertek pada suatu graph.

Demo Program