Dijkstra: 20 phút uống cà phê viết ra thuật toán chạy ngầm trong cả thế giới

TL;DR

• Edsger Dijkstra nghĩ ra thuật toán shortest path trong 20 phút uống cà phê ở Amsterdam năm 1956, không bút không giấy, ban đầu chỉ để demo máy ARMAC.
• Khi bạn mở Google Maps, gửi gói tin qua internet, hay bị NPC trong game truy đuổi - cốt lõi vẫn là logic Dijkstra: luôn mở rộng nút có chi phí thấp nhất trước.
• Mikkel Thorup khẳng định mọi phát triển lý thuyết về shortest path từ 1959 đều xây dựng trên thuật toán này. Năm 2024 giới khoa học máy tính chứng minh nó đạt universal optimality.
• Các biến thể hiện đại - A-star, Contraction Hierarchies, breakthrough Duan 2025 - chỉ thay đổi lớp tối ưu, không thay đổi tinh thần gốc.

Quán cà phê Amsterdam 1956

Câu chuyện bắt đầu rất bình thường. Một buổi sáng năm 1956, Edsger Wybe Dijkstra - nhà khoa học máy tính người Hà Lan, 26 tuổi - đi mua sắm cùng vị hôn thê ở Amsterdam. Hai người mệt, ghé vào một quán cà phê terrace ngồi nghỉ.

Trong lúc chờ cà phê, Dijkstra nghĩ về một bài toán đang phải giải: tìm cách demo khả năng của máy tính mới ARMAC bằng một vấn đề đủ trực quan để báo chí hiểu được. Ông chọn bài toán tìm đường ngắn nhất giữa hai thành phố Hà Lan trên bản đồ 64 nút.

Không có bút, không có giấy. Toàn bộ thuật toán được nghĩ trong đầu, trong 20 phút uống cà phê. Sau này Dijkstra giải thích chính sự thiếu giấy bút đã giúp ông: "Without pencil and paper you are almost forced to avoid all avoidable complexities" - không có bút giấy buộc bạn phải tránh mọi sự phức tạp không cần thiết. via Quanta Magazine.

Phải đến 3 năm sau, năm 1959, Dijkstra mới chịu công bố - và chỉ vì một đồng nghiệp khuyên ông nên publish. Ông cảm thấy thuật toán quá đơn giản, không xứng đáng đăng tạp chí.

Ý tưởng cốt lõi

Bài toán Dijkstra giải nghe rất ngắn gọn: cho một đồ thị có trọng số dương trên các cạnh, tìm đường đi ngắn nhất từ một điểm xuất phát đến mọi điểm còn lại - bài toán Single Source Shortest Path.

Cách thuật toán hoạt động giống cách con người tìm đường. Bạn đứng ở điểm A, nhìn xung quanh và đánh giá: đường này gần, đường kia xa. Bạn chọn đi theo hướng gần nhất trước. Từ điểm mới đó, bạn lại nhìn xung quanh và tiếp tục chọn hướng tốt nhất. Mỗi lần bạn tìm thấy đường ngắn hơn đến một điểm nào đó, bạn cập nhật lại ước tính.

Dijkstra làm đúng như vậy nhưng không bỏ sót khả năng nào. Khi đến đích, tính chất toán học của thuật toán đảm bảo con đường tìm được là ngắn nhất tuyệt đối - không có cách nào tốt hơn. Erik Demaine ở MIT mô tả ngắn gọn: "It's a great algorithm. It's very fast, simple and easy to implement".

Tại sao thuật toán này trường tồn

Hầu hết thuật toán nổi tiếng đều sống vì nó phức tạp đến mức người khác chưa nghĩ ra. Dijkstra sống vì lý do ngược lại: nó đơn giản đến mức gần như không thể cải thiện ý tưởng cốt lõi.

Mikkel Thorup, nhà khoa học máy tính tại Đại học Copenhagen, viết trong paper năm 1999: "Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm" - mọi phát triển lý thuyết về bài toán shortest path từ 1959 đều xây dựng trên thuật toán của Dijkstra. via Quanta Magazine.

Năm 2024, một nhóm nghiên cứu công bố chứng minh Dijkstra đạt universal optimality. Nói nôm na: với bài toán shortest path không âm, không tồn tại thuật toán nào nhanh hơn Dijkstra một cách phổ quát. 70 năm rồi vẫn chưa ai đánh bại được nó về mặt lý thuyết.

Mọi nơi đều có Dijkstra

Cái hay của bài toán shortest path là đồ thị có trọng số có thể là bất cứ thứ gì. Đổi định nghĩa nút và trọng số là có một ứng dụng mới.

• Google Maps và GPS: nút là giao lộ, cạnh là đường, trọng số là thời gian di chuyển ước tính có tính mật độ giao thông thời gian thực. Google Maps hiện đại ghép Dijkstra với Contraction Hierarchies, A-star Search, mạng neural train trên 20 năm dữ liệu giao thông, và telemetry từ 2 tỷ thiết bi - nhưng nhân vẫn là Dijkstra.
• Mạng Internet: giao thức routing OSPF (Open Shortest Path First) và IS-IS chạy trong gần như mọi router xương sống chính là Dijkstra. Mỗi router build shortest path tree đến mọi router khác trong autonomous system của mình.
• Game pathfinding: NPC truy đuổi bạn dùng A-star, là Dijkstra cộng thêm hàm heuristic ước lượng khoảng cách còn lại đến đích. Nhanh hơn nhiều trong thực tế nhưng vẫn giữ tính chất "tìm ra đường ngắn nhất".
• Logistics, đặt vé: tìm chặng bay rẻ nhất, chuỗi cung ứng tối ưu, tuyến giao hàng - đều mô hình hoá thành đồ thị có trọng số và chạy Dijkstra (hoặc biến thể).
• Sinh học phân tử: mạng tương tác protein, nút là protein, trọng số là xác suất tương tác - dùng để tìm pathway sinh hoá.

Biến thể hiện đại và breakthrough mới

70 năm phát triển sau Dijkstra không xoá bỏ thuật toán, chỉ thêm các lớp tối ưu:

• A-star (1968): thêm heuristic hướng tới đích để bỏ qua các nhánh vô vọng. Mặc định cho game và robotics.
• Bidirectional Dijkstra: chạy hai instance đồng thời từ nguồn và đích, gặp nhau ở giữa - tiết kiệm trung bình một nửa nút phải duyệt.
• Contraction Hierarchies: preprocess đồ thị thành nhiều lớp thứ bậc, query Google Maps trên bản đồ toàn cầu xong trong vài chục mili giây.
• Duan et al. 2025: nhóm Ran Duan công bố thuật toán break được sorting barrier đã đứng yên từ 1984, đạt O(m * log^(2/3) n) cho directed SSSP. "Điều này có thể đã được phát hiện 50 năm trước, nhưng nó đã không" - Mikkel Thorup bình luận.

Tất cả đều giữ nguyên tinh thần Dijkstra: luôn mở rộng nút có chi phí tốt nhất trước. Sự khác biệt là cách chọn "nút tốt nhất" và cách tổ chức dữ liệu.

Kết

Lần tới khi bạn bấm chỉ đường trên Google Maps, lúc gói tin chat nhảy qua hai chục router trước khi đến server, lúc một con NPC trong game tìm đường vòng để đuổi theo bạn - hãy nhớ có một người Hà Lan 26 tuổi từng ngồi uống cà phê ở Amsterdam 20 phút và không cần bút giấy.

Đó có lẽ là một trong những 20 phút có ROI cao nhất trong lịch sử khoa học máy tính.