🚨 41 năm phát triển — và Dijkstra không còn là không thể đánh bại. Một nhóm từ Tsinghua, Stanford và MPI for Informatics đã đạt được thuật toán xác định đầu tiên phá vỡ giới hạn O(m + n log n) cho các đường đi ngắn nhất từ một nguồn trong các đồ thị có hướng với trọng số thực không âm. 💡 Thời gian chạy mới: O(m log^(2/3) n) 📜 Thời gian chạy tốt nhất cũ: Dijkstra + Fibonacci heap = O(m + n log n) Chìa khóa? Một sự kết hợp giữa ý tưởng "biên giới" của Dijkstra và sự thư giãn của Bellman-Ford, với một mẹo phân vùng biên giới đệ quy giúp giữ cho heap nhỏ — tránh rào cản sắp xếp cổ điển. Tác động: ⚡ Tính toán lại GPS nhanh hơn 🚦 Dòng giao thông mượt mà hơn 📦 Giao hàng rẻ hơn 🌐 Định tuyến mạng nhanh hơn 📚 Đã đến lúc viết lại chương thuật toán về SSSP Tăng tốc thực sự đầu tiên cho SSSP có hướng kể từ năm 1984 — và nó là xác định.