Algoritma Bellman-Ford

2.1.3. Algoritma Bellman-Ford 

Algoritma Bellman-Ford merupakan algoritma untuk mencari shortest path,dengan menghitung jarak terpendek pada sebuah diagraf berbobot, atau menghitung semua jarak terpendek yang berawal dari satu titik node.

Langkah-langkah:

1.Tentukan vertex source dan daftar seluruh vertices maupun edges.

2.Assign nilai untuk distance dari vertex source = 0, dan yang lain infinite

3.Mulailah iterasi terhadap semua vertices yang dimulai dari vertex source,

4.Untuk menentukan distance dari semua vertices yang berhubungan dengan vertex source dengan formula seperti berikut ini :

- U = vertex asal

- V = vertex tujuan

- UV = Edges yang menghubungkan U dan V

- Jika distance V, lebih kecil dari distance U + weight UV maka distance V, diisi dengan distance U + weight UV

- Lakukan hingga semua vertices terjelajahi

5.Untuk mengecek apakah ada negative cycle dalam graf tersebut lakukan iterasi untuk semua edges yang ada, kemudia lakukan pengecek an seperti dibawah ini :

6.Untuk semua edges UV, jika ada distance vertex U + weight edges UV kurang dari distance vertex V maka sudah jelas bahwa graf tersebut memiliki negative cycle.

Contoh :

Dari graph di atas tentukan lintasan terpendek dari titik 1 ke titik 4.

Langkah-langkah:

1.Tahap pertama adalah tahap inisialisasi yaitu dengan melabeli titik awal atau titik asal yaitu titik 1 dengan 0 dan titik-titik lainnya dengan ∞.d(1,1) ← 0 untuk masing-masing v anggota V

 – {s} maka d (s,v) ← ∞

 2.Tahap kedua yaitu tahap proses iterasi

Untuk masing-masing sisi (1,2) anggota E maka

Jika d(1,2) > d(1,2)+w(2,3) maka

d(1,2) diganti dengan d(1,2)+w(2,3)

Akhirnya diperoleh d(1,4)=5+4+4=13.