Contoh algoritma Bellman – Ford yang digunakan pada graf 5 titik
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. Algoritme Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritme Bellman-Ford hanya digunakan jika ada sisi berbobot negatif.
Algoritme Bellman-Ford menggunakan waktu sebesar O(V.E), di mana V dan E adalah banyaknya sisi dan titik.
Dalam konteks ini, bobot ekivalen dengan jarak dalam sebuah sisi.
// Definisi tipe data dalam grafrecord titik {
list sisi2
real jarak
titik sebelum
}
record sisi {
titik dari
titik ke
real bobot
}
function BellmanFord(list semuatitik, list semuasisi, titik dari)
// Argumennya ialah graf, dengan bentuk daftar titik // and sisi. Algoritme ini mengubah titik-titik dalam // semuatitik sehingga atribut jarak dan sebelum// menyimpan jarak terpendek.// Persiapanfor each titik v in semuatitik:
if v is dari then v.jarak = 0
else v.jarak:= tak-hingga
v.sebelum:= null// Perulangan relaksasi sisifor i from 1 to size(semuatitik):
for each sisi uv in semuasisi:
u:= uv.dari
v:= uv.ke // uv adalah sisi dari u ke vif v.jarak > u.jarak + uv.bobot
v.jarak:= u.jarak + uv.bobot
v.sebelum:= u
// Cari sirkuit berbobot(jarak) negatiffor each sisi uv in semuasisi:
u:= uv.dari
v:= uv.ke
if v.jarak > u.jarak + uv.bobot
error "Graph mengandung siklus berbobot total negatif"
Secara umum coding algoritme dapat juga menggunakan teknikcoding pemrograman yang lain.
Artikel bertopik komputer ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.
