Hi, I am

Ngô Tôn

I am a programmer.

Home / HCMUS / Graph Theory / Tìm đường đi ngắn nhất với Dijkstra, Floyd, Bellman

Tìm đường đi ngắn nhất với Dijkstra, Floyd, Bellman

1.    Thuật toán Dijkstra

Cho G=(X,E) là một đồ thị có trọng không âm gồm n đỉnh. Thuật toán Dijkstra được dùng để tìm

đường đi ngắn nhất từ đỉnh i đến j cho trước.

Gọi L là ma trận trọng lượng (với qui ước Lhk = +∞ nếu không có cạnh nối từ đỉnh h đến đỉnh k). Ta sử dụng thêm hai mảng để lưu vết của quá trình tìm đường đi:

  • Dodai[…] : lưu độ dài từ đỉnh đầu i đến các đỉnh trong đồ thị.
  • Nhan[…] : lưu đỉnh liền trước nó trên đường đi.
Chú ý: Khi thuật toán dừng, nếu Dodai[j] = +∞ thì không tồn tại đường đi từ i đến j, nếu ngược lại thì Dodai[j] là độ dài đường đi ngắn nhất.

2.    Thuật toán Floyd

Cho G=(X, E) là một đồ thị có trọng không âm gồm n đỉnh. Thuật toán Floyd được dùng để tìm

đường đi ngắn nhất giữa tất cả cặp đỉnh bất kỳ của một đồ thị G.

Gọi L là ma trận trọng lượng (với qui ước Lhk = 0 nếu không có cạnh nối từ đỉnh h đến đỉnh k). Ta sử dụng thêm một ma trận nxn để lưu vết của quá trình tìm đường đi:

–     sau_nut1[i,j] : lưu chỉ số của đỉnh ngay sau i trên đường đi từ i đến j.

Đỉnh k được gọi là trung gian của i, j nếu nó có đường đi từ i→k và k→j.Chú ý:

  • Khi thuật toán kết thúc, nếu Lij = 0 thì không tồn tại đường đi từ i đến j, nếu ngược lại thì Lij là độ dài đường đi ngắn nhất.
  • Trong cách làm ở trên, việc xuất ra đường đi chỉ cần duyệt một khoảng từ j→k có đỉnh trung gian hay không vì từ i→k không có đỉnh trung gian nào.
  • Ta có thể không cần khởi tạo ma trận lưu chỉ số sau_nut1 như ở trên (set bằng 0). Như vậy trong bước 2, chỉ lưu giá trị trung gian đơn giản như sau: sau_nut1[i,j] = k . Tuy nhiên, việc xuất ra đường đi từ i đến j chúng ta phải tiến hành duyệt hai khoảng i→k và k→j để kiểm tra xem có đỉnh nào làm trung gian bên trong hai khoảng này nữa không.

3.    Thuật toán Bellman

Khác với thuật toán Dijkstra và Floyd, Bellman giải quyết được cả trường hợp đồ thị có cạnh âm. Thuật toán còn phát hiện được cả trường hợp đồ thị có chu trình âm. Từ một đỉnh x cho trước, thuật toán Bellman cho phép xác định đường đi ngắn nhất đến tất cả các đỉnh trong đồ thị.

Nhận xét rằng đường đi ngắn nhất (không chứa chu trình âm) từ một đỉnh x đến một đỉnh y trong một đồ thị có n đỉnh chi đi qua tối đa n đỉnh. Thuật toán Bellman bước 0 bắt đầu với giả thiết rằng từ đỉnh x, nếu đi qua tối đa là 1 đỉnh (kể cả đỉnh xuất phát) ta sẽ chỉ đến được đỉnh x với chi phí là 0. Bước 1, nếu đi qua tối đa là 2 đỉnh, ta sẽ đến được các đỉnh trong bước 0 và các đỉnh i (sao cho có cung nối trực tiếp từ một đỉnh j thuộc bước 0 đến i)…

Trong quá trình mở rộng mỗi bước, tại mỗi đỉnh đã đi đến được i đã, ta sẽ lưu lại đỉnh cha thỏa mãn điều kiện đường đi ngắn nhất đến i. Sau đây là một ví dụ minh họa cho thuật toán Bellman.

Cho trước đồ thị có hướng G (có thể chứa cạnh âm). Tìm đường đi xuất phát từ đỉnh x đến tất cả các đỉnh trong đồ thị.

 

Bước 0: step = 0

mincost[step][i] = ∞, i ≠ x mincost[step][x] = 0

Để có thể lưu lại đường đi, ngắn nhất, ta cần thêm mảng previous để lưu lại đường đi

previous[step][x] = x (bằng chính nó)

Bước 2: step++;

nếu step ≥ n thì dừng thuật toán(*)

mincost[step][i] = min( mincost[step-1][i], min({mincost[step-1][j]+a[j][i]})

), i,j

Với a[j][i] == ∞ nếu không có cung nối

previous[step][i] =:

·      j nếu đường đi ngắn nhất đi qua trung gian j rồi đến i

·      i nếu đường đi đến i đã tối ưu

Bước 3: Nếu

mincost[step][i] == mincost[step-1][i], i

mọi đường đi đã được tối ưu, dừng thuật toán.

Ngược lại, quay lại bước 2.

(*): Nếu như chúng ta đã đi qua đủ n đỉnh nhưng vẫn chưa tối ưu được đường đi, ta có thể kết luận được đồ thị có chu trình âm.

Không như khi cài đặt các thuật toán Dijkstra, Floy, 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ị VOCUC, vì nếu như chi phí đạt đến ngưỡng này, có thể xem như tràn số.

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.

Source code (C++)

About ngoton

Ngô Tôn is a programmer with passion for tailored software solutions. Comes with 7+ years of IT experience, to execute beautiful front-end experiences with secure and robust back-end solutions.

Check Also

Biểu diễn và thao tác trên đồ thị

Mục lục 3.1.  Lưu trữ3.2.  Đọc và xuất đồ thị3.3.  Kiểm tra đồ thị không …

Leave a Reply

avatar
  Subscribe  
Notify of