40
2.5.2.4 Algoritma Bellman – Ford
Menurut
Horowitz
(1998,
p270),
Algoritma Bellman
Ford
adalah
algoritma
untuk menemukan shortest path dari suatu verteks awal menuju semua
verteks yang ada pada graph berarah yang berbobot. Algoritma ini menggunakan
rumus:
dist
k
[u] = min {dist
k-1
[u], min {dist
k-1
[i] + cost [i] [u]}}
n = jumlah node
k = 2,3,…n-1
Hasil dari perhitungan rumus diatas dimasukkan dalam suatu
tabel,
sehingga pada iterasi tertentu akan dapat dilihat jarak terpendeknya.
1
10
2
30
100
5
50
50
10
3
20
4
Gambar 2.10 Contoh Graph untuk Algoritma Bellman Ford
k=1
Pada
k
=
1
dilakukan
inisialisasi jarak
pada
node
yang
langsung terhubung ke
node asal (node 1) sehingga didapatkan:
dist¹ [1] = 0, dist [2] = 10, dist¹ [3] = ~, dist¹ [4] = 30, dist¹ [5] =100
 |