Algoritma Bellman Ford

Algoritma Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah graf 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. Muncul nya Algoritma ini cukup membantu jika bobot dari suatu graf bernilai negatif.

Pengaplikasian algoritma bellman ford dalam routing:

Dalam routing algoritma Bellman-Ford adalah digunakan dalam distance vector routing protocol, misalnya Routing Information Protocol (RIP). Algoritma ini didistribusikan karena melibatkan jumlah node (router) dalam Autonomous system, koleksi jaringan IP biasanya dimiliki oleh ISP. Adapun langkah-langkah nya sebagai berikut:

• Setiap node menghitung jarak antara dirinya dan semua node lain dalam AS dan menyimpan informasi ini sebagai sebuah tabel.

• Setiap node mengirimkan tabel ke semua node tetangga.

• Ketika sebuah node menerima tabel jarak dari tetangganya, ia menghitung rute terpendek ke semua node lainnya dan update tabel sendiri untuk menggambarkan perubahan yang terjadi

Kelemahan utama dari algoritma Bellman-Ford adalah sebagai berikut:

•  Kurang baik untuk jaringan berskala besar

•  Perubahan topologi jaringan tidak berjalan dengan cepat karena update tersebar node-by-node.

• Menghitung sampai tak terhingga (jika link atau node mengalami sebuat kegagalan maka node tidak dapat dicapai dari beberapa set node lain, node yang lain dapat menghabiskan waktu untuk looping sampai tak terhingga secara bertahap meningkatkan perkiraan mereka dari kegagalan itu, dan sementara itu mungkin ada routing loop).

Contoh algoritma bellman ford :

 Langkah Pertama

Langkah Kedua

Langkah Ketiga

 

Langkah Keempat

 

Langkah Kelima

 

Langkah Keenam

 

Langkah Ketujuh

 

Referensi : http://users.informatik.uni-halle.de/~jopsi/dinf503/chap12.shtml