Thuật toán Johnson tìm DDNN giữa mọi cặp đỉnh trong đồ thị

 Ngày gửi bài: 23/03/2009 Số lượt đọc: 234
Thuật toán Johnson tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh với độ phức tạp là O(V2LgV+VE). Với đồ thị thưa, nó tốt hơn là việc lặp đi lặp lại việc điều chỉnh các ma trận hay thuật toán FLOYD-WARSHALL. Thuật toán cho kết quả trả về ma trận trọng số đường đi ngắn nhất giữa tất cả các cặp đỉnh hay báo cáo về đồ thị nhập vào có chứa chu trình âm (chu trình âm là 1 chu trình trong đồ thị có tổng trọng số các đỉnh thuộc chu trình là 1 số âm, nếu trong đồ thị có chu trình âm, ta cứ đi trên chu trình ấy vô số lần thì ta sẽ có DDNN vô cùng bé ). Thuật toán Johnson sử dụng cả 2 chương trình con là thuật toán Dijkstra và thuật toán Bellman –Ford (tôi không trình bày 2 thuật toán này nữa).
Thuật toán Johnson sử dụng kĩ thuật “Gán lại trọng số” (REWEIGHTING). Nếu tất cả các trọng số W của các đỉnh trong 1 đồ thị G = (V,E) đều không âm (V là tập đỉnh của đồ thị, E là tập cạnh của đồ thị, W là hàm trọng số trên mỗi đỉnh), ta có thể tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh bằng cách chạy thuật toán Dijkstra lần lượt cho từng đỉnh, với cấu trúc dữ liệu Fibonacci-heap hàng đợi ưu tiên nhỏ nhất, độ phức tạp thuật toán để tìm DDNN giữa tất cả các cặp đỉnh vào khoảng O(V2LgV+VE). Nếu G có trọng số ở đỉnh âm nhưng không tạo thành chu trình âm, ta đơngiản tính toán bằng cách tạo mới 1 đỉnh có trọng số không âm, điều này cho phép chúng ta sử dụng cùng 1 phương pháp. Trọng số mới W’ của đỉnh phải thoả mãn 2 tính chất quan trọng sau:
1.Với mọi cặp đỉnh u,v thuộc V, 1 đường đi p là DDNN từ u đến v sử dụng hàm trọng số W nếu và chỉ nếu p cũng là DDNN từ u đến v sử dụng hàm trọng số W’.
2.Với mọi cặp đỉnh (u,v), trọng số mới W’(u,v) phải không âm.
Bạn thấy ngay, đồ thị G xác định với hàm trọng số mới W’ có thể thi hành với O(VE).
Giữ nguyên DDNN bằng REWEIGHTING
Dựa vào các bổ đề, ta có thể dễ dàng chứng minh việc REWEIGHTING thoả mãn tính chất đầu tiên. Ta sử dụng hàm C để biểu thị trọng số DDNN bằng hàm trọng số W và C’ để biểu thị trọng số DDNN bằng hàm trọng số W’.
Bổ đề 1 - REWEIGHTING không làm thay đổi các đường đi ngắn nhất
Cho 1 ma trận trọng số, đồ thị G = (V,E) với hàm trọng số W: E -> R, hàm H : V->R đối với bất cứ 1 đỉnh nào đều mang giá trị thực. Với mỗi cặp (u,v) thuộc E, ta định nghĩa W’(u,v)=W(u,v) + H(u) – H(v). Với p = {v0 ,v1, …, vk} là đường đi từ đỉnh v0 đến đỉnh vk. Và p là đường đi ngắn nhất từ đỉnh v0tới đỉnh vk với hàm trọng số W nếu và chỉ nếu đó cũng là đường đi ngắn nhất với hàm trọng số W’. Đó là, W(p) = C(v0, vk) nếu và chỉ nếu W’(p) = C’(v0, vk). G có 1 chu trình âm sử dụng hàm trọng số W nếu và chỉ nếu G có 1 chu trình âm sử dụng hàm trọng số W’.
Chứng Minh:
Ta sẽ chứng minhW’(p) = W(p) + H(v0) – H(vk). (*)



(vì tổng thu gọn H(v0) - H(vk) = H(v0) - H(v1) + H(v1)-H(v2) + … + H(vk-1) - H(vk))
Bởi vậy, bất cứ đường đi p nào từ v0đến vk đều có W’(p) = W(p) + H(v0) - H(vk). Nếu 1 đường đi từ v0đến vk là đường đi ngắn nhất trong các đường sử dụng hàm trọng số W, thì nó cũng là DDNN sử dụng W’. Như vậy, W(p) = C(v0, vk) nếu và chỉ nếu W’(p) = C’(v0, vk).
Cuối cùng, ta thấy rằng G có chu trình âm trên hàm trọng số W nếu và chỉ nếu G có chu trình âm trên hàm trọng số W’. Để ý thấy bất cứ chu trình c={v0, v1,… vk} với v0 = vk. Với đẳng thức (*), W’(c) = W(c) +