46
•
Untuk setiap pasangan simpul i, j pada V, perhatiakm semua lintasan dari i ke j
dimana
semua
simpul
pertengahan diambil
dari
{1,
2,
...,
k},
dan
p
adalah
lintasan berbobot minimum diantara semuanya.
•
Algoritma
ini
mengeksploitasi relasi
antara
lintasan p
dan
lintasan
terpendek
dari
i
ke j dengan semua simpul pertengahan berada pada himpunan {1, 2, ...,
k-1}.
•
Relasi
tersebut
bergantung
pada
apakah
k
adalah
simpul
pertengahan
pada
lintasan p.
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)
Procedure Floyd-Warshall :
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
 |