Algoritma Floyd-Warshall

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Langsung ke: navigasi, cari

Algoritma Floyd-Warshall menghitung jarak terpendek untuk semua pasangan titik pada sebuah graf, dan melakukannya dalam waktu berorde kubik.

Algoritma[sunting | sunting sumber]

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 melakukannya sekaligus untuk semua pasangan titik. Algoritma ini berjalan dengan waktu Θ(|V|3).

Dasar algoritma ini adalah observasi berikut:

--belum diterjemahkan--

Implementasi algoritma ini dalam pseudocode: (Graf direpresentasikan sebagai matrix keterhubungan, yang isinya ialah bobot/jarak sisi yang menghubungkan tiap pasangan titik, dilambangkan dengan indeks baris dan kolom) (Ketiadaan sisi yang menghubungkan sebuah pasangan dilambangkan dengan Tak-hingga)

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
}

Aplikasi dan Generalisasi[sunting | sunting sumber]

--belum diterjemahkan--

Implementasi[sunting | sunting sumber]

Referensi[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]