Bellman Ford

Algotima Bellman ford adalah salah satu algoritma untuk mencari shostest path dimana jika dalam dalam suatu graf terdapat edge yang bernilai negatif. Meski demikian algoritma bellman ford juga bisa digunakan untuk mencari shortest path dalam graf yang hanya memiliki posotife edges, akan tetapi tidak akan seefisien algortima djikstra. Agar lebih jelas, perhatikan contoh dibawah ini :Maka jika kita menggunakan algortima bellman untuk menghitung jarak terdekat vertex A ke vertex C adalah 5, akan tetapi jarak terpendek sesungguhnya adalah 1, yaitu dengan jalur A – B – C, seperti gambar di bawah ini:

Hal ini dapat diantisipasi dengan menggunakan algoritma bellman. Dalam algoritma bellman class vertex harus memiliki 2 field yaitu distance(yang menunjukan jarak terdekat vertex tersebut terhadap vertex source) dan predecessor (yaitu c=vertex yang mendahului vertex tersebut pada path yang terbentuk) Akan tetapi algoritma bellman memiliki suatu kelemahan terdapat graf yang memiliki negative cycle, sehingga untuk graf yang memilki negative cycle memang tidak dapat dihitung shortest pathnya.

Contoh Implementasi Algoritma Bellman Ford
Langkah 1
Pertama dimulai dari node "0" yang akan menyebarkan informasi ke masing masing node yang langsung berhubungan dengan node "0" tersebut sesuai dengan nilai bobot jalurnya.

Langkah 1

Langkah 2
Semua node yang sudah memiliki nilai akan menyebarkan informasi ke node yang saling berhubungan langsung, kemudian jika sebuah node diisi oleh lebih dari 1 nilai maka nilai yang dipilih yaitu nilai yang terkecil.

Langkah 3
Lakukan berulang langkah 2 sampai terbentuknya nilai pada setiap node yang sudah static (tidak berubah lagi).

Gambar langkah langkah penyelesaian akan seperti berikut:

Langkah 2

Langkah 3

Langkah 4

Langkah 5

Langkah 6

Referensi:
www.wikipedia.com
www.csufresno.edu