Algoritma Floyd-Warshall

Algoritma Floyd-Warshall memiliki input graf berarah dan berbobot (V, E), yang berupa daftar titik (node/vertex V) dan daftar sisi (edge E). 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 melakukan sekaligus untuk semua pasangan titik terpendek diantara semua pasangan simpul. Algoritma ini mengijinkan bobot sisi negatif. Langkah-langkah dari algoritma Floyd-Warshall adalah sebagai berikut (Budiarsyah dan Dibi Khairurrazi , 2010) :

1. Langkah awal

    Untuk menentukan shortest path dengan menggunakan algoritma Floyd Warshall adalah dengan merepresentasikan suatu graf sebagai suatu matriks berbobot.  Format output berupa matriks n x n berjarak D = [dij] dimana dij merupakan jarak dari vertex  i ke j. 

2. Langkah kedua

    melakukan dekomposisi Floyd-Warshall dengan urutan : 

•      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} 

•      dij(0) dikumpulkan pada wij, yaitu tidak ada vertex intermediate. 

•      D(k)  menjadi matriks n x n [dij(k)] 

•      Tentukan dij(n) sebagai jarak dari i ke j kemudian hitung D(n) 

•      Hitung D(k) untuk k = 0,1,...., n 

3. Langkah ketiga

    Menentukan struktur shortest path. Dalam hal ini, harus dilakukan dua pengamatan terlebih dahulu sebelum melangkah lebih jauh, yaitu : 

•    Sebuah shortest path tidak memuat vertex yang sama sebanyak dua kali 

•    Untuk sebuah shortest path dari i ke j dengan beberapa vertex intermediate pada path dipilih dari kumpulan {1, 2, ...., k}, dengan kemungkinan :

a)    k bukan merupakan vertex pada path (path terpendek memiliki panjang dij(k-1)).

b)    k merupakan vertex pada path (path terpendek memiliki panjang dij(k-1) + dij(k-1)). 

•    Setelah melakukan pengamatan diatas, kemudian dlakukan penentuan shortest path dari i ke j yang memuat vertex k. 

•    Shortest path tersebut memuat sebuah subpath dari i ke k dan sebuah subpath dari k ke j. 

•    Setiap subpath hanya dapat memuat vertex intermediate pada {1, ..., k-1} dan sedapat mungkin memiliki nilai terpendek, kemudian beri nama panjangnya dik(k-1) dan dkj(k-1) sehingga path  memiliki panjang dik(k-1)  + dkj(k-1). 

4. Langkah terakhir

Melakukan iterasi yang dimulai dari iterasi ke 0 sampai dengan n. Perhitungan yang dilakukan adalah : 

•    Menentukan D(0)  (iterasi ke 0) = [wij] merupakan matriks bobot. 

•    Menentukan D(k)  dengan menggunakan rumus ,  dij(k)  = min {dij(k-1), dik(k-1) + dkj(k-1)}, untuk k = 1, ..., n dimana n adalah jumlah vertex. 

Hasil akhir dari algoritma Floyd-Warshall adalah matriks untuk iterasi ke n. Dari matriks ke-n ini, dapat dilihat shortest path untuk setiap vertex pada suatu graph.

Posted in: ANDROID,REKAYASA PERANGKAT LUNAK