Thuật toán BELLMAN FORD tìm đường đi ngắn nhất

Xin chào tất cả các bạn,Ở các bài trước các bạn đã biết được các thuật toán như Dijkstra , Floy và bài hôm này Phong sẽ giới thiệu cho các bạn thuật toán tìm đường đi ngắn nhất khác, đó là thuật toán bellman ford.Tương tự như các bài khác ta lướt sơ qua một số lý thuyết nhé.hii.

Thuật toán 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 Dijsktra giải cùng bài toán này tuy nhiên Dijsktra 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 O(V·E), trong đó V là số đỉnh và E là số cung của đồ thị.

Ư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.
Ví dụ tìm đường đi ngắn nhất từ đỉnh B tới đỉnh D của đồ thị G
 
Đồ 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 0
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 1
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 2
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 3
Bước 4: Bước 4 giống bước 3 nên thuật toán dừng.
 
Bước 4
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

Một ví dụ khác qua hình ảnh dưới đây:

Đọc tới đây các bạn đã hình dung được thuật toán này chạy như thế nào chưa nè,chúng ta đi qua mã giả của nó nhé!

 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"

Đọc đoạn mã giả ở trên xong là hông biết gì luôn phải hông nè,hii.

Đoạn mã đó chúng ta chỉ cần tập trung vào cái if là ok.Câu if này thể hiện nếu có cạnh nó sẽ dán nhãn đỉnh nó đi qua cũng với trọng số.Việc này lặp đi lặp lại n lần thì sẽ hoàn thành .Nó tương tự như dijsktra và nhanh như floy phải hông nè.Nó khá giống với dijsktra phải hông nè.hii.

Các bạn tham khảo đoạn code dưới đây xem nó hoạt động như thế nào nhé!

Mình chúc các bạn hoàn thành xong thuật toán này nhé,chúc các bạn có mùa giáng sinh vui vẻ, hạnh phúc, ấm áp bên gia đình và người thân nhé! À đừng quên là nếu có thắc mắc gì thì đừng ngại comment nhé bạn thân! hii

Lưu ý là thuật toán trên mình tự code nên chắc chắn không thể không có sai sót nên mong các bạn thông cảm và chỉ dùng để tham khảo thôi nhé.

Giấy phép Creative Commons Giấy phép Creative Commons Attribution-ShareAlike 4.0 Quốc tế .

Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :