Thuật toán Bellman–Ford

Thuật toán Bellman–Ford hay Giải thuật Bellman–Ford là một thuật toán tính các đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng có trọng số (trong đó 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 tuy nhiên Dijkstra có thời gian chạy nhanh hơn, đơn giản là đòi hỏi trọng số của các cung phải có giá trị không âm.

Thuật toán Bellman–Ford chạy trong thời gian formula_1, trong đó "V" là số đỉnh và "E" là số cung của đồ thị.
== Tư tưởng thuật toán ==
- Bước 1: Khởi tạo formula_2 và formula_3.
- Bước 2: Với mỗi formula_4 ta đặt:

formula_5
- Bước 3: Nếu formula_6 với formula_4 thì formula_8 chính là độ dài đường đi ngắn nhất từ x đến i. Ngược lại nếu k < n thì tăng k = k+1 và trở lại bước 2; nếu k = n thì dừng vì từ x đi tới được 1 mạch âm.

Ưu điểm:

Từ 1 đỉnh xuất phát nhìn hình ta có thế suy ra đường đi ngắn nhất từ đỉnh đó tới các đỉnh khác mà không cần làm lại từ đầu.

Ví dụ: Từ đỉnh 1 ta có thể tìm đường đi ngắn nhất từ 1->3 và 1->4 mà không cần làm lại.

== Chứng minh tính đúng đắn ==
Tính đúng đắn của thuật toán có thể được chứng minh bằng quy nạp. Thuật toán có thể được phát biểu chính xác theo kiểu quy nạp như sau:

Bổ đề. Sau "i" lần lặp vò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ài của một đường đi nào đó từ "s" tới "u";
2. Nếu có một đường đi từ "s" tới "u" qua nhiều nhất "i" cung, thì Khoảng_cách(u) có giá trị không vượt quá độ dài của đường đi ngắn nhất từ "s" tới "u" qua tối đa "i" cung.

Chứng minh

Trường hợp cơ bản: Xét codice_1 và thời điểm trước khi vòng "for" được chạy lần đầu tiên. Khi đó, với đỉnh nguồn codice_2, điều này đúng. Đối với các đỉnh "u" khác, codice_3, điều này cũng đúng vì không có đường đi nào từ "nguồn" đến "u" qua 0 cung.

Trường hợp quy nạp:

Chứng minh câu 1. Xét thời điểm khi khoảng cách tới một đỉnh được cập nhật bởi công thức
codice_4. Theo giả thiết quy nạp, codice_5 là độ dài của một đường đi nào đó từ "nguồn" tới "u". Do đó, codice_6 là độ dài của đường đi từ "nguồn" tới "u" rồi tới "v".

Chứng minh câu 2: Xét đường đi ngắn nhất từ "nguồn" tới "u" qua tối đa "i" cung. Giả sử "v" là đỉnh liền ngay trước "u" trên đường đi này. Khi đó, phần đường đi từ "nguồn" tới "v" là đường đi ngắn nhất từ "nguồn" tới "v" qua tối đa "i-1" cung. Theo giả thuyết quy nạp, codice_7 sau "i-1" vòng lặp không vượt quá độ dài đường đi này. Do đó, codice_8 có giá trị không vượt quá độ dài của đường đi từ "s" tới "u". Trong lần lặp thứ "i", codice_5 được lấy giá trị nhỏ nhất của codice_10 với mọi "v" có thể. Do đó, sau "i" lần lặp, codice_5 có giá trị không vượt quá độ dài đường đi ngắn nhất từ "nguồn" tới "u" qua tối đa "i" cung.

Khi "i" bằng số đỉnh của đồ thị, mỗi đường đi tìm được sẽ là đường đi ngắn nhất toàn cục, trừ khi đồ thị có chu trình âm. Nếu tồn tại chu trình âm mà từ đỉnh nguồn có thể đi đến được thì sẽ không tồn tại đường đi nhỏ nhất (vì mỗi lần đi quanh chu trình âm là một lần giảm trọng số của đường).

== Ứng dụng trong định tuyến ==
Một biến thể phân tán của thuật toán Bellman-Ford được dùng trong các giao thức định tuyến vector khoảng cách, chẳng hạn giao thức RIP ("Routing Information Protocol"). Đây là biến thể phân tán vì nó liên quan đến các nút mạng (các thiết bị định tuyến) trong một hệ thống tự chủ ("autonomous system"), ví dụ một tập các mạng IP thuộc sở hữu của một nhà cung cấp dịch vụ Internet (ISP).

Thuật toán gồm các bước sau:

1. Mỗi nút tính khoảng cách giữa nó và tất cả các nút khác trong hệ thống tự chủ và lưu trữ thông tin này trong một bảng.
2. Mỗi nút gửi bảng thông tin của mình cho tất cả các nút lân cận.
3. Khi một nút nhận được các bảng thông tin từ các nút lân cận, nó tính các tuyến đường ngắn nhất tới tất cả các nút khác và cập nhật bảng thông tin của chính mình.

Nhược điểm chính của thuật toán Bellman-Ford trong cấu hình này là
- Không nhân rộng tốt
- Các thay đổi của tô-pô mạng không được ghi nhận nhanh do các cập nhật được lan truyền theo từng nút một.
- Đếm dần đến vô cùng (nếu liên kết hỏng hoặc nút mạng hỏng làm cho một nút bị tách khỏi một tập các nút khác, các nút này vẫn sẽ tiếp tục ước tính khoảng cách tới nút đó và tăng dần giá trị tính được, trong khi đó còn có thể xảy ra việc định tuyến thành vòng tròn)

== Minh họa bằng hình ==
Tìm đường đi ngắn nhất từ đỉnh B tới đỉnh D của đồ thị G

- Bước 0: Ta đánh dấu đỉnh xuất phát = 0, các đinh còn lại bằng vô cực.

- Bước 1:

Tại đỉnh A có đỉnh B đi vào có chi phí hiện tại (2) < chi phí trước (∞) => cập nhật lại chi phí đỉnh A

Tại đỉnh C có đỉnh B đi vào có chi phí hiện tại (6) < chi phí trước (∞) => cập nhật lại chi phí đỉnh C

- Bước 2:

Tại đỉnh C có đỉnh A đi vào có chi phí hiện tại (5) < chi phí trước (6) => cập nhật lại chi phí đỉnh C

Tại đỉnh D có đỉnh C đi vào có chi phí hiện tại (8) < chi phí trước (∞) => cập nhật lại chi phí đỉnh D

- Bước 3:

Tại đỉnh D có đỉnh A đi vào có chi phí hiện tại (7) < chi phí trước (8) => cập nhật lại chi phí đỉnh D

- Bước 4:

Bước 4 giống bước 3 nên thuật toán dừng.

- Kết luận:

Có đường đi ngắn nhất từ B->D: B->A->C->D

- Lưu ý:

Nếu bước 4 không giống bước 3 => kết luận không có đường đi ngắn nhất từ B->D

==Cài đặt Bellman==
Hàm khởi tạo (bước 0)

Không như khi cài đặt thuật toán Dijkstra, do Bellman chấp nhận cạnh âm, việc sử dụng trị -1 không còn đúng nữa. Tạm thời, ta có thể sử dụng trị MAXINT (32767) cho giá trị inf, vì nếu như chi phí đạt đến ngưỡng này, có thể xem như tràn số.

Cài đặt hàm Bellman

Chú ý rằng để có thể kết luận được đồ thị có chu trình âm hay không. ta cần chạy đến bước thứ n (nghĩa là đi qua tối đa n+1 đỉnh). Do đó, cấu trúc dữ liệu để lưu cũng cần lưu ý khi khai báo.

Cấu trúc dữ liệu

Hàm in kết quả

Nếu nStep = n+1, ta kết luận đồ thị có chu trình âm.

Ngược lại, ta sẽ dò chi phí ngược từ bước nStep-1 đến bước 0 (Do bước nStep có giá trị giống bước nStep-1).

==Tham khảo==
- Tài liệu lý thuyết bộ môn Lý Thuyết Đồ Thị, trường Đại học Khoa học Tự nhiên
- Richard Bellman: "On a Routing Problem", in Quarterly of Applied Mathematics, 16(1), pp. 87–90, 1958.
- Lestor R. Ford jr., D. R. Fulkerson: "Flows in Networks", Princeton University Press, 1962.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman-Ford algorithm, pp. 588–592.