Arsitektur & Routing Internet

Algoritma 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. 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. Untuk langkah langkah dalam algoritma bellman ford adalah sebagai berikut ini :

Tentukan vertex source dan daftar seluruh vertices maupun edges.
Assign nilai untuk distance dari vertex source = 0, dan yang lain infinite
Mulailah iterasi terhadap semua vertices yang dimulai dari vertex source,
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

Untuk mengecek apakah ada negative cycle dalam graf tersebut lakukan iterasi untuk semua edges yang ada, kemudia lakukan penge-cek-an seperti dibawah ini :
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.