07.2 - Đồ thị có trọng số

Giới thiệu

Như đã đề cập trong mục 7.1, rõ ràng các phương án duyệt BFS thông thường trên đồ thị không trọng số không thể áp dụng vào đồ thị có trọng số để tìm đường đi ngắn nhất vì có thể có nhiều con đường đi qua nhiều đỉnh hơn nhưng lại có tổng trọng số nhỏ hơn đường đi qua ít đỉnh. Cho đến nay, hai thuật toán phổ biến nhất để giải quyết bài toán này là Dijkstra và Bellman-Ford. Trong mục này chúng ta sẽ thảo luận về hai thuật toán này cùng một số cải tiến của chúng trong những trường hợp đặc biệt.

Thuật toán Dijkstra - đồ thị không có trọng số âm

Được đề xuất bởi nhà khoa học máy tính Edsger W. Dijkstra  vào năm 1956, đây là thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số không âm kinh điển nhất, dù theo thời gian đã xuất hiện nhiều biến thể và cải tiến độ phức tạp. Mục đích chính của thuật toán là tìm đường đi ngắn nhất từ đỉnh nguồn s đến tất các các đỉnh còn lại. Dựa trên tư tưởng tham lam, thuật toán ban đầu khởi tạo tất cả đỉnh có đường đi ngắt nhất từ s là ∞   . Bắt đầu từ đỉnh nguồn s, nó cập nhật đường đi ngắn nhất cho các đỉnh kề trực tiếp với nó dựa trên trọng số các cạnh tương ứng. Tuy nhiên, nó sẽ lựa chọn cạnh có trọng số nhỏ nhất để đi tiếp. Ở các bước tiếp theo, quy trình cũng thực hiện tương tự nhưng sẽ có thao tác cập nhật lại giá trị đường đi ngắn nhất nếu từ một đỉnh u đến một đỉnh v mà đường đi ngắn nhất đến u + w[u, v] < đường đi ngắn nhất đến v thì ta cập nhật lại giá trị đường đi ngắn nhất cho v rồi gán cha của v là u. Thuật toán kết thúc khi tất cả các đỉnh đều đã được thăm hết.

Ví dụ: Cho đồ thị sau đây

Dựa trên ý tưởng trên, ta có thể tóm tắt thuật toán Dijkstra qua mã giả sau:

Ghi chú:

• dist[u]: danh sách chứa khoảng cách ngắn nhất từ s đến u

• prev[v]: đỉnh trước cua v trên đường đi ngắn nhất

• Q: hàng đợi ưu tiên chứa các đỉnh được thăm

 1  function Dijkstra(Graph, source):

 2     

 3      for each vertex v in Graph.Vertices:

 4          dist[v] ← INFINITY

 5          prev[v] ← UNDEFINED

 6          add v to Q

 7      dist[source] ← 0

 8     

 9      while Q is not empty:

10          u ← vertex in Q with minimum dist[u]

11          remove u from Q

12         

13          for each neighbor v of u still in Q:

14              alt ← dist[u] + Graph.Edges(u, v)

15              if alt < dist[v]:

16                  dist[v] ← alt

17                  prev[v] ← u

18

19      return dist[], prev[]

Nguồn: Wikipeadia

Cài đặt

Trong cài đặt thực tế, người ta luôn tìm cấu trúc dữ liệu phù hợp cho việc lưu các đỉnh kế với đỉnh đang xét đồng thời phải lấy được đỉnh có khoảng cách đường đi ngắn nhất một cách nhanh chóng. Như vậy, thực tế chúng ta phải lưu một cặp (dist[u], u) vào thùng chứa đó. Hàng đợi ưu tiên sẵn có trong thư viện chuẩn của C++, Python và Java đều có thể cho ta lấy được đỉnh tốt nhất trong thời gian ngắn nhưng lại không thể cập nhật khóa một khi nó đã ở trong đó (khóa ở đây chính là dist[u] - chúng ta đang muốn cập nhật nó). Như vậy, thay vì dùng hàng đợi ưu tiên như trong mô tả của giải thuật, chúng ta sẽ dùng Set. Thao tác cập nhật sẽ là chúng ta lấy ra và xóa cặp cũ, cập nhật key rồi add ngược trở lại. Vì được xây dựng dựa trên cây nhị phân cân bằng (Binary search balance tree), Set có thể cho ta làm được điểu này. Trong khi cấu trúc đống nhị phân (Binary Heap) của hàng đợi ưu tiên không làm được.

Các bạn tham khảo đoạn code sau:

Độ phức tạp

Quá trình duyệt tựa như BFS, nên với cách lưu đồ thị bằng danh sách kề, ta sẽ tốn O(|V|+|E|) cho thao tác duyệt, với mỗi lần duyệt ta phải đẩy vào, lấy ra, cập nhật trong hàng đợi nên tốn O(log|V|).

==> Độ phức tạp tổng: O(|V| + |E|)log|V|)

Phiên bản cải tiến cho thuật toán Dijkstra

Nếu chúng ta quen với việc cài đặt tự nhiên theo mô tả của giải thuật, tức quen với việc dùng hàng đợi ưu tiên hơn. Chúng ta có thể tham khảo qua phiên bản cải tiến của thuật toán Dijkstra.

Trong phiên bản này, tức nhiên dùng hàng đợi ưu tiên để lưu các đỉnh cần thăm, thay vì xóa đỉnh khỏi hàng đợi rồi add ngược trở lại đỉnh đó với khoảng cách tốt hơn vào set, ta sẽ add tiếp tục đỉnh đó với phiên bản tốt hơn vào priority_queue (pq). 

Rõ ràng, trong pq sẽ tồn tại nhiều hơn 1 cặp có cùng giá trị đỉnh nhưng khác khóa (độ dài). Sự cải tiến ở đây là mỗi lần lấy một đỉnh trong pq ra, ta sẽ kiểm tra khóa của nó có lớn hơn khoảng cách của nó (đang được lưu ở mảng dist[]) hay không, nếu đúng như vậy thì ta bỏ qua.

Thuật toán cải tiến này tức nhiên chạy chậm hơn phiên bản gốc về thực tế. Nhưng độ phức tạp tổng quát vẫn là O((|V|+|E|)log|V|)

Đồ thị có trọng số âm

Chúng ta quan sát đồ thị sau đây, trọng số âm ở cạnh (2, 3)

Với hai phiên bản cài đặt ở trên của thuật toán Dijkstra, phiên bản dùng set (phiên bản đầu) sẽ không thể tính ra được độ dài đường đi chính xác độ dài ngắn nhất từ 0-->4. Chương trình sẽ bị lỗi không xác định do thao tác tìm (find) giá trị cũ của đỉnh 3 trong set để xóa nó sẽ không tìm ra.

Với phiên bản cải tiến, chương trình cài đặt dùng priority_queue sẽ thực hiện được do nó không thực sự xóa đi các giá trị cũ mà vẫn giữ trong queue.

Nhiệm vụ 1. Cài đặt thử 2 phiên bản với testcase trên để xem kết quả

Đồ thị có chu trình âm

Phiên bản cải tiến ở trên cũng chỉ giải quyết được trong trường hợp đồ thị có trọng số nhưng không có chu trình âm. Vì nếu có chu trình âm, phiên bản cải tiến sẽ bị dính vào một vòng lặp vô tận vì vì sẽ push vào queue pair mới với đường đi tốt hơn mãi mãi. Ví dụ quan sát đồ thị sau đây.

Đỉnh 1, 2 và hai cung (1, 2) (2,1) tạo thành một chu trình âm với trọng số w =15 - 42 = -27. Các đường đi mới đến đỉnh 1 với giá trị tốt hơn sẽ liên tục được push vào queue không thể dừng được.

Thuật toán Bellman-Ford

Được phát triển bởi hai nhà khoa học máy tính Richard Ernest Bellman và Lester Randolph Ford, ý tưởng của thuật toán đơn giản là co tất cả các cạnh V-1 lần. Nghĩa là:

Ban đầu, cũng gán dist[0] = 0 và dist[v] = ∞ với tất cả v ∈  V. Sau đó với các đỉnh u kế với 0, ta co hết thàng trọng số cạnh (0,u). Với mỗi đỉnh u đó, ta lại xét đến các định v kề với nó và tiếp tục co hết. Các em tham khảo đoạn code sau:

Độ phức tạp

Thuật toán Bellman-Ford tốn O(V^3) nếu đồ thị được biểu diễn dạng ma trận kề và O(VE) nếu là danh sách kề. Rõ ràng nó chậm hơn Dijkstra rất nhiều, cho nên người ta ít dùng nó tìm đường đi ngắn nhất trong trường hợp bình thường. Tuy nhiên nếu đồ thị nhỏ và có chứa chu trình âm, thì việc dùng thuật toán Bellman-Ford là một lựa chọn tốt.

Không chỉ có thể tính được đường đi ngắn nhất từ nguồn đến các đỉnh, nó còn có thể dùng để kiểm tra đồ thị có tôn tại chu trình âm hay không. Bằng cách chạy lại thuật toán một lần nữa, nếu tồn tại đỉnh nào có đường đi ngắn hơn ban đầu của nó chứng tỏ có tồn tại chu trình âm. Vì theo các chứng minh, nếu một đồ thị không chứa chu trình âm, thì một khi đã tìm được đường đi ngắn nhất tới tất cả các đỉnh, thì dù chạy lại bao nhiều lần bằng Dijkstra hay Bellman, chúng ta không thể co đường đi của nó được nữa.

Nhiệm vụ 2. Kattis - Đường đi ngấn nhất 1

Nhiệm vụ 3. UVa 01112 - Mice and Maze

Nhiệm vụ 4. UVa 10986  - Sending email

Nhiệm vụ 5. UVa 00558 - Wormholes

Nhiệm vụ 6. UVa 10449 - Traffic