41
2.11
Algoritma Bellman-Ford (negative weighted problem)
Algoritma
Bellman-Ford
menghitung jarak
terpendek
(dari
satu
sumber)
pada
sebuah
digraf
berbobot. Maksudnya
dari
satu
sumber
ialah
bahwa
ia
menghitung semua
jarak terpendek
yang berawal dari
satu
titik
node.
Algoritma
Dijkstra
dapat
lebih
cepat
mencari
hal
yang
sama
dengan
syarat
tidak
ada
sisi
(edge)
yang
berbobot
negatif.
Maka
Algoritma
Bellman-Ford
hanya
digunakan
jika ada sisi berbobot negatif.
Skema Pencarian Lintasan Terpendek dengan algoritma Bellman Ford
Gambar 2.7 Contoh graf berbobot negatif
Gambar 2.8 Tahap pertama Algoritma Bellman-Ford
untuk penyelesaian contoh graf pada gambar 1
 |