Thuật toán Bellman-Ford

Tư tưởng thuật toán

- Bước 1: Khởi tạo ∏(0,x)=0; ∏(0,i)=+∞, ∀i≠x và k=1
- Bước 2: Với mỗi i∈X ta đặt:

    ∏(k,i)=min({∏(k-1,i)}∪{∏(k-1,j)+L[j][i]})
- Bước 3: Nếu ∏(k,i)=∏(k-1,i) với i∈X thì ∏(k,i) 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.

Nội dung thuật toán

function BellmanFord(danh_sách_đỉnh, danh_sách_cung, nguồn)
   // hàm yêu cầu đồ thị đưa vào dưới dạng một danh sách đỉnh, một danh sách cung
   // hàm tính các giá trị khoảng_cách và đỉnh_liền_trước của các đỉnh, 
   // sao cho các giá trị đỉnh_liền_trước sẽ lưu lại các đường đi ngắn nhất.

   // bước 1: khởi tạo đồ thị
   for each v in danh_sách_đỉnh:
       if v is nguồn then khoảng_cách(v):= 0
       else khoảng_cách(v):= vô cùng
       đỉnh_liền_trước(v):= null
   
   // bước 2: kết nạp cạnh
   for i from 1 to size(danh_sách_đỉnh)-1:       
       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)
               đỉnh_liền_trước(v):= u

   // bước 3: kiểm tra chu trì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 trình âm"

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 C đ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 các thuật toán dijkstra, Floyd, 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ố.
step = 0; for {i...} {

  mincost[step][i] = inf;

  previous[step][i] = i;
} mincost[step][x] = 0;
Cài đặt hàm Bellman
Chú y 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.
bSuccess = false;
for (step = 1; step <=n; step ++) // dùng <=n thay vì <n
{

  for(i...)
  {
     mincost[step][i] = mincost[step-1][i]
     previous[step][i] = previous[step-1][i]
     // tìm các đỉnh j có đường nối từ j -->i
     // và chi phí bước step-1 của j khác vô cực
     for (j...)
     if (...&&...)
     {
        // cập nhật lại nếu chi phí bước step của i là vô cực
        // hoặc chi phí đi qua j: mincost[step-1][j]+a[j][i]
        //tối ưu hơn
        if (...||...)
        {
           // cập nhật lại chi phí và lưu đỉnh cha
        }
      }
   }
   // so sánh mincost[step] với mincost[step-1], nếu bằng nhau
   // kết thúc thành công
   int bSame = true;
   for (i...)
   if (mincost[step][i]!= mincost[step-1][i])
   {
      bSame = false;
      break;
    // đã giống nhau,đường đi đã tối ưu
    if (bSame)
       break;
}
Cấu trúc dữ liệu
int mincost [MAX+1][MAX];
int previous[MAX+1][MAX];
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)
k = y;
for (i=nStep-1;i>0;i--) // chừa lại bước cuối
{

  printf("%d <---", k);
  k = previous[i][k];    // đỉnh trước k
}
printf("%dn",k); // có thể thêm kiểm tra k == x