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.