Apa yang anda ketahui tentang Algoritma Floyd-Warshall ?

matematika_diskrit

(Bima Satria) #1

Algoritma Floyd-Warshall

Algoritma Floyd-Warshall merupakan algoritma yang digunakan untuk mencari lintasan terpendek pada sebuah graf berbobot dengan bobot positif atau negatif (namun tidak memiliki siklus negatif).

Apa yang anda ketahui tentang Algoritma Floyd-Warshall ?


(Karla Amanda) #2

Algoritma Floyd-Warshall adalah sebuah algoritma analisis graf untuk mencari bobot minimum dari graf berarah. Algoritma Floyd-Warshall adalah matriks hubung graf berarah berlabel, dan keluarannya adalah path terpendek dari semua titik ke titik yang lain (Kamayudi, A. 2009).

Dalam usaha untuk mencari path 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. Misalkan

𝑊𝑊0 adalah matriks hubung graf berarah berlebel mula-mula. 𝑊𝑊∗ adalah matriks hubung minimal dengan 𝑊𝑊𝑖𝑖𝑗𝑗 ∗ = path terpendek dari titik 𝑣𝑣𝑖𝑖 ke 𝑣𝑣𝑗𝑗 .[4]

Algoritma Warshall untuk mencari path terpendek adalah sebagai berikut

image

Dalam iterasinya untuk mencari path terpendek, Algoritma Warshall membentuk n matriks sesuai dengan iterasi-k. Hal ini menyebabkan waktu prosesnya lambat, terutama untuk n yang besar. Meskipun waktu prosesnya bukanlah yang tercepat, Algoritma Warshall sering dipergunakan untuk menghitung path terpendek karena kesederhanaannya.

Program implementasinya Algoritma Warshall sangat mudah dibuat.

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