Giai thuat floy

Thu?t toán Bellman-Ford là m?t thu?t toán tính các du?ng di ng?n nh?t ngu?n don trong m?t d? th? có hu?ng có tr?ng s? (trong dó m?t s? cung có th? có tr?ng s? âm). Thu?t toán Dijkstra gi?i cùng bài toán này v?i th?i gian ch?y th?p hon, nhung l?i ḍi h?i tr?ng s? c?a các cung ph?i có giá tr? không âm. Do dó, thu?t toán Bellman-Ford thu?ng ch? du?c dùng khi có các cung v?i tr?ng s? âm.

Thu?t toán Bellman Ford ch?y trong th?i gian O(V·E), trong dó V là s? d?nh và E là s? cung c?a d? th?.
M?c l?c
[gi?u]

* 1 N?i dung thu?t toán
* 2 Ch?ng minh tính dúng d?n
* 3 ?ng d?ng trong d?nh tuy?n
* 4 Cài d?t
o 4.1 C
* 5 Tham kh?o

N?i dung thu?t toán

function BellmanFord(danh_sách_d?nh, danh_sách_cung, ngu?n)
// hàm yêu c?u d? th? dua vào du?i d?ng m?t danh sách d?nh, m?t danh sách cung
// hàm tính các giá tr? kho?ng_cách và d?nh_li?n_tru?c c?a các d?nh,
// sao cho các giá tr? d?nh_li?n_tru?c s? luu l?i các du?ng di ng?n nh?t.

// bu?c 1: kh?i t?o d? th?
for each v in danh_sách_d?nh:
if v is ngu?n then kho?ng_cách(v) := 0
else kho?ng_cách(v) := vô cùng
d?nh_li?n_tru?c(v) := null

// bu?c 2: k?t n?p c?nh
for i from 1 to size(danh_sách_d?nh):
for each (u,v) in danh_sách_cung:
if kho?ng_cách(v) > kho?ng_cách(u) + tr?ng_s?(u,v) :
kho?ng_cách(v) := kho?ng_cách(u) + tr?ng_s?(u,v)
d?nh_li?n_tru?c(v) := u

// bu?c 3: ki?m tra chu tŕnh âm
for each (u,v) in danh_sách_cung:
if kho?ng_cách(v) > kho?ng_cách(u) + tr?ng_s?(u,v) :
error "Đ? th? ch?a chu tŕnh âm"

Ch?ng minh tính dúng d?n

Tính dúng d?n c?a thu?t toán có th? du?c ch?ng minh b?ng quy n?p. Thu?t toán có th? du?c phát bi?u chính xác theo ki?u quy n?p nhu sau:

B? d?. Sau i l?n l?p ṿng for:

1. N?u Kho?ng_cách(u) không có giá tr? vô cùng l?n, th́ nó b?ng d? dài c?a m?t du?ng di nào dó t? s t?i u;
2. N?u có m?t du?ng di t? s t?i u qua nhi?u nh?t i cung, th́ Kho?ng_cách(u) có giá tr? không vu?t quá d? dài c?a du?ng di ng?n nh?t t? s t?i u qua t?i da i cung.

Ch?ng minh.

Tru?ng h?p co b?n: Xét i=0 và th?i di?m tru?c khi ṿng for du?c ch?y l?n d?u tiên. Khi dó, v?i d?nh ngu?n kho?ng_cách(ngu?n) = 0, di?u này dúng. Đ?i v?i các d