Tăng Tốc Cho Dijkstra - Kata Learns To Code

Thuật toán Dijkstra có độ phức tạp là N^2 (N là số đỉnh của đồ thị), trong một bài toán nếu ta chạy Dijkstra chỉ một hoặc vài lần thì thời gian không phải là vấn đề, tuy nhiên khi cần chạy Dijkstra rất nhiều lần thì ta phải cài đặt lại Dijkstra sao cho tốc độ của nó được nhanh hơn. Không thể dùng Floyd được vì số đỉnh quá lớn, trong bài viết này chúng ta sẽ dùng ma trận trọng số cho đơn giản, còn thực sự khi số đỉnh lên tới vài nghìn thì phải dùng danh sách liên kết.

Thuật toán Dijkstra gốc

Cấu trúc dữ liệu

• Đỉnh xuất phát là S
• a: array[1..N, 1..N] of integer — là ma trận trọng số của đồ thị đã cho
• mark: array[1..N] of boolean — dùng để đánh dấu xem một đỉnh đã có nhãn cố định hay chưa
• d: array[1..N] of integer — d[i] là nhãn của đỉnh i, nó là độ dài đường đi ngắn nhất hiện thời từ S đến i
• dad: array[1..N] of integer — dùng để ghi nhận đỉnh đi kề trước trên đường đi

Thuật toán

Khởi tạo:

• mark[i] = true hết trừ mark[S] = false
• d[i] = a[S, i]
• dad[i] = S

Lặp lại N lần các công việc sau:

• tìm đỉnh K có nhãn chưa cố định và nhãn là nhỏ nhất (*)
• đánh dấu K thành nhãn cố định (mark[K] = false)
• tìm xem có đỉnh V nào nhãn chưa cố định, có cạnh nối tới K và d[V] > d[K] + a[K, V] thì d[V] = d[K] + a[K, V] và dad[V] = K

Cải tiến Dijkstra

Chúng ta hãy để ý tới bước (*), để tìm ra đỉnh K như vậy bình thường ta phải duyệt qua N đỉnh. Tại sao ta không dùng cấu trúc Heap, như vậy ta sẽ lấy ra được ngay K ở đầu Heap, đưa đuôi của Heap lên đầu và vun lại Heap, thao tác vun chỉ mất cỡ logarith cơ số 2 của độ dài Heap. Tốc độ sẽ được cải thiện đáng kể!

Điểm qua chút về tính chất của Heap: Heap là một cấu trúc cây nhị phân trong đó giá trị ở nút cha luôn bé hơn hoặc bằng giá trị ở mỗi hai nút con. Dễ thấy nút ở đầu Heap (nút gốc) là có giá trị bé nhất trong toàn Heap. Trong quá trình xài, vài nút trong Heap bị thay đổi giá trị (gọi là nút k đi), khi đó tính chất Heap bị phá vỡ và ta phải hiệu chỉnh lại Heap, có hai thủ tục cơ bản để làm điều này là downheap(k) và upheap(k). Cụ thể hơn nữa về Heap các bạn xem trong các sách về thuật toán căn bản.

Trở lại Dijkstra cải tiến, phần khởi tạo có thêm phần tạo Heap, chú ý rằng lúc này mảng d đã bị xáo trộn, d[i] không còn là nhãn của đỉnh i nữa mà là nhãn của index[i] nghĩa là ta phải dùng thêm một mảng phụ index để theo dõi sự xáo trộn này, index được khởi tạo là index[i] = i. Bây giờ thì không cần mảng mark nữa vì chỉ có các phần tử trong Heap thì mới có nhãn chưa cố định. Và thuật toán Dijkstra viết lại như sau:

Khởi tạo:

• d[i] = a[S, i]
• dad[i] = S
• index[i] = i (1 <= i <= N)
• tạo Heap

Lặp lại N lần các công việc sau:

• đỉnh K = index[1] trở thành có nhãn cố định, sao lưu d[1]: tmp = d[1]
• loại bỏ nút 1 (nút gốc) ra khỏi Heap bằng cách đưa nút cuối Heap lên thay thế và giảm kích thước Heap đi 1 đơn vị, hiệu chỉnh Heap bằng cách gọi downheap(1)
• tìm xem có đỉnh V nào trong Heap, có cạnh nối tới K và d[V] > tmp + a[K, index[V]] thì:
  • d[V] = tmp + a[K, index[V]]
  • dad[index[V]] = K
  • upheap(V)
  • downheap(V)

Mình đã cài đặt bằng Pascal (rất tiếc lâu rồi nên không còn giữ source code) và chạy thấy rất nhanh, nhanh hơn nhiều so với cài đặt thông thường. Dĩ nhiên cái giá phải trả là cài đặt phức tạp hơn.

Share this:

• Facebook
• LinkedIn
• More

• Email
• Twitter
• Tumblr

Like Loading...

Related