Đường đi ngắn nhất xuất phát từ một đỉnh, thuật toán Ford_bellman
Phần lớn các thuật toán tìm khoảng cách giữa hai đỉnh s và t được xây dựng nhờ kỹ thuật tính toán mà ta có thể mô tả đại thể như sau: từ ma trận trọng số a[u,v], u,v ∈ V, ta tính cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v ...
Phần lớn các thuật toán tìm khoảng cách giữa hai đỉnh s và t được xây dựng nhờ kỹ thuật tính toán mà ta có thể mô tả đại thể như sau: từ ma trận trọng số a[u,v], u,v ∈ V, ta tính cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v ∈ V. Mỗi khi phát hiện
d[u] + a[u,v] < d[v] (1)
cận trên d[v] sẽ được làm tốt lên: d[v] + a[u,v].
Quá trình đó sẽ kết thúc khi nào chúng ta không làm tốt thêm được bất kỳ cận trên nào. Khi đó, rõ ràng giá trị của mỗi d[v] sẽ cho khoảng cách từ đỉnh s đến đỉnh v. Khi thể hiện kỹ thuật tính toán này trên máy tính, cận trên d[v] sẽ được gọi là nhãn của đỉnh v, còn việc tính lại các cận này sẽ được gọi là thủ tục gán. Nhận thấy rằng để tính khoảng cách từ s đến t, ở đây, ta phải tính khoảng cách từ s đến tất cả các đỉnh còn lại của đồ thị. Hiện nay vẫn chưa biết thuật toán nào cho phép tìm đường đi ngắn nhất giữa hai đỉnh làm việc thực sự hiệu quả hơn những thuật toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại.
Sơ đồ tính toán mà ta vừa mô tả còn chưa xác định, bởi vì còn phải chỉ ra thứ tự các đỉnh u và v để kiểm tra điều kiện (1). Thứ tự chọn này có ảnh hưởng rất lớn đến hiệu quả của thuật toán.
Bây giờ ta sẽ mô tả thuât toán Ford-Bellman tìm đường đi ngắn nhất từ đỉnh s đến tất cả các đỉnh còn lại của đồ thị. Thuật toán làm việc trong trường hợp trọng số của các cung là tuỳ ý, nhưng giả thiết rằng trong đồ thị không có chu trình âm.
(* Đầu vào:
Đồ thị có hướng G=(V,E) với n đỉnh,
s ∈ V là đỉnh xuất phát, A[u,v], u, v ∈ V, ma trận trọng số;
Giả thiết: Đồ thị không có chu trình âm.
Đầu ra:
Khoảng cách từ đỉnh s đến tất cả các đỉnh còn lại d[v], v ∈ V.
Trước[v], v ∈ V, ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v.*)
begin
(* Khởi tạo *)
for v ∈ V do
begin
d[v]:=a[s,v];
Truoc[v]:=s;
end;
d[s]:=0;
for k:=1 to n-2 do
for v ∈ V{ s} do
for u ∈ V do
if d[v] > d[u] +a[u,v] then
begin
d[v]:=d[u]+a[u,v];
Truoc[v]:=u;
end;
end;
Tính đúng đắn của thuật toán có thể chứng minh trên cơ sở trên nguyên lý tối ưu của quy hoạch động. Rõ ràng là độ phức tạp tính toán của thuật toán là O(n3). Lưu ý rằng chúng ta có thể chấm dứt vòng lặp theo k khi phát hiện trong quá trình thực hiện hai vòng lặp trong không có biến d[v] nào bị đổi giá trị. Việc này có thể xảy ra đối với k<n-2, và điều đó làm tăng hiệu quả của thuật toán trong việc giải các bài toán thực tế. Tuy nhiên, cải tiến đó không thực sự cải thiện được đánh giá độ phức tạp của bản thân thuật toán. Đối với đồ thị thưa tốt hơn là sử dụng danh sách kề Ke(v), v∈ V, để biểu diễn đồ thị, khi đó vòng lặp theo u cần viết lại dưới dạng
For u ∈ Ke(v) do
If d[v] > d[u] + a[u,v] thenBegin
D[v]:=d[u]+a[u,v];Truoc[v]:=u;
End;
Trong trường hợp này ta thu được thuật toán với độ phức tạp O(n,m).
xét đồ thị trong hình 7.1. Các kết quả tính toán theo thuật toán được mô tả trong bảng dưới đây
| ∞ | 2 | ∞ | ∞ | ∞ | |
| ∞ | ∞ | 3 | 3 | 8 | |
| A= | ∞ | ∞ | ∞ | 1 | -5 |
| ∞ | ∞ | ∞ | ∞ | ∞ | |
| ∞ | ∞ | ∞ | 4 | ∞ |
Hình 7.1. Minh họa thuật toán Ford_Bellman.
| k | d[1] Truoc[1] | d[2] Truoc[2] | d[3] Truoc[3] | d[4] Truoc[4] | d[5] Truoc[5] |
| 0, 1 | 1, 1 | ∞, 1 | ∞, 1 | 3, 1 | |
| 1 | 0, 1 | 1, 1 | 4, 2 | 4, 2 | -1, 3 |
| 2 | 0, 1 | 1, 1 | 4, 2 | 3, 5 | -1, 3 |
| 3 | 0, 1 | 1, 1 | 4, 2 | 3, 5 | -1, 3 |
Bảng kết quả tính toán theo thuật toán Ford_Bellman
Trong các mục tiếp theo chúng ta sẽ xét một số trường hợp riêng của bài toán tìm đường đi ngắn nhất mà để giải chúng có thể xây dựng những thuật toán hiệu quả hơn thuật toán Ford_Bellman. Đó là khi trọng số của tất cả các cung là các số không âm hoặc là khi đồ thị không có chu trình
