45
for each sisi uv in semuasisi:
u := uv.dari
v := uv.ke
if v.jarak > u.jarak + uv.bobot
error "Graph mengandung siklus berbobot total negatif"
Algoritma Bellman-Ford menggunakan waktu sebesar O(V.E), di mana V
dan E adalah banyaknya sisi dan titik :
Inisialisasi: O(v)
Loop utama: O(v.e)
Pengecekan loop negative: O(e)
Total: O(v.e)
2.12
Algoritma Floyd-Warshall (all pairs source problem).
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.
Dasar algoritma ini adalah sebagai berikut:
•
Asumsikan
semua
simpul
graf
berarah
G
adalah
V
=
{1,
2,
3,
4,
...,
n},
perhatikan subset {1, 2, 3, ..., k}.
 |