Pengertian Algoritma Bellman Ford

Algoritme Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah digraf berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma Bellman-Ford menggunakan waktu sebesar O(V.E), di mana V dan E adalah menyatakan banyaknya sisi dan titik. Dalam konteks ini, bobot ekivalen dengan jarak dalam sebuah sisi. (Bayu Aditya Pradhana, 2006).

Algoritma Bellman-Ford yang ditemukan oleh Richard E. Bellman, seorang ahli matematika yang terlahir di New York 1920.

Source Image :http://a2c2.org/category/awards/richard-e-bellman-control-heritage-award?page=2

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