Dijkstra Heap cải tiến

Như đã biết, trong các kì thi, thuật toán Dijkstra thường được cài
bằng cấu trúc Binary Heap hoặc priority_queue của C++, cách cài
đặt này cho độ phức tạp là \(O((E+V)\log V)\), \(E\) là số cạnh,
\(V\) là số đỉnh.

Với một số bài, cách này sẽ không chạy được trong thời gian cho phép
(Ví dụ bài TOURS13). Trong trường
hợp đó ta có thể dùng Fibonacci Heap để đạt được độ phức tạp là
\(O(E+V\log V)\), tuy nhiên cách cài này rất phức tạp, không phù
hợp để sử dụng khi thi.

Bài viết này sẽ giới thiệu một kĩ thuật cải tiến Dijkstra Heap thông
thường để có độ phức tạp tương đương với Fibonacci Heap.

Mô tả thuật toán

Trước tiên ta xét một cách cài đặt Dijkstra hơi khác như sau:

Ở bước sửa nhãn, thay vì sửa nhãn đỉnh v: \(d(v) = d(u) + c(u, v)\) rồi cập
nhật lại heap, ta thêm một cặp \((v, d(u)+c(u, v))\) vào heap.

Trong bước cố định nhãn, ta chỉ cần tìm phần tử \((u, c)\) có đỉnh \(u\)
chưa được cố định nhãn và \(c\) nhỏ nhất.

Từ cách cài đặt trên, ta có thể cải tiến như sau: trước tiên ta sắp xếp danh
sách kề của mỗi đỉnh theo trọng số cạnh tăng dần. Ở bước sửa nhãn, ta thấy không
cần thêm tất cả các đỉnh kề với u vào heap mà chỉ cần thêm đỉnh có trọng số
cạnh nhỏ nhất, sau khi đỉnh đó bị loại ra khỏi heap thì ta mới thêm đỉnh tiếp
theo trong danh sách kề. Cách cải tiến này sẽ giúp giảm bớt số thao tác update
trên heap.

Đánh giá thuật toán

Phần sắp xếp lại cạnh có độ phức tạp khoảng \(O(E\log E)\).

Phần thuật toán Dijkstra có độ phức tạp trong trường hợp tốt nhất là \(O(V\log V)\)
hoặc \(O(V\log E)\) tùy theo cách cài đặt, và trong trường hợp xấu nhất là \(O(E\log V)\).

Vì vậy thuật toán này chỉ hiệu quả hơn trong trường hợp cần chạy Dijkstra nhiều lần.

Cài đặt

Xem cài đặt trong code của bài TOURS13.