Nhóm nghiên cứu của Đại học Thanh Hoa (Tsinghua University) đã hợp tác với Đại học Stanford và đạt được bước tiến lớn về mặt độ phức tạp tính toán đối với bài toán đường đi ngắn nhất truyền thống (single-source shortest path, SSSP). Nghiên cứu này đã giành giải Best Paper tại hội nghị STOC 2025.
Phương pháp được dùng phổ biến theo truyền thống là thuật toán Dijkstra, với độ phức tạp thời gian có dạng O(m + n log n) (n = số nút, m = số cạnh).
Hạng tử log n liên quan đến hàng đợi ưu tiên (priority queue) hoặc sắp xếp (sorting), và trong 40 năm qua chưa có cải tiến nào vượt qua được phần này.
Thuật toán mới đã giảm độ phức tạp thời gian xuống O(m · log^(2/3) n).
Vì log^(2/3) n tăng chậm hơn log n (tức là tăng ít hơn log n), nên khi số lượng nút rất lớn, khác biệt sẽ trở nên đáng kể.
Chưa có bình luận nào.