Thuật toán Dijkstra tìm đường đi ngắn nhất từ một điểm đến mọi điểm khác trong một mạng đường có độ dài, bằng cách "loang" dần từ điểm xuất phát: mỗi bước chốt điểm gần nhất chưa chốt, rồi cập nhật khoảng cách cho các điểm láng giềng. Nhà khoa học máy tính người Hà Lan Edsger Dijkstra nghĩ ra nó năm 1956, công bố năm 1959, và ý tưởng ấy đến nay vẫn nằm trong lõi của nhiều phần mềm dẫn đường, định tuyến mạng.
Hai mươi phút ở quán cà phê
Theo lời Dijkstra kể lại nhiều năm sau, một buổi sáng năm 1956 ông cùng vợ đi mua sắm ở Amsterdam, ghé một quán cà phê ngoài trời và nghĩ ra thuật toán trong khoảng hai mươi phút, không cần giấy bút. Ông cần một ví dụ để trình diễn chiếc máy tính mới của Trung tâm Toán học Amsterdam cho công chúng không chuyên — và "tìm đường ngắn nhất giữa hai thành phố Hà Lan" là bài toán ai cũng hiểu. Bài báo ba trang của ông in năm 1959.
Dijkstra sau này nói rằng việc không có giấy bút buộc ông phải tìm một cách thật đơn giản. Có lẽ vì thế mà thuật toán dễ dạy đến mức ngày nay sinh viên tin học năm nhất nào cũng học.
Bài toán
Cho một mạng gồm các điểm (giao lộ, thành phố) nối nhau bằng các đoạn đường, mỗi đoạn có độ dài hoặc thời gian đi — trong ngôn ngữ đồ thị là đồ thị có trọng số. Từ điểm xuất phát S, tìm đường ngắn nhất tới đích T. Yêu cầu quan trọng: không có đoạn đường nào có độ dài âm — điều hiển nhiên với đường thật.
Số đường đi có thể có giữa hai điểm tăng khủng khiếp theo kích thước mạng. Thử hết mọi đường là không thể. Dijkstra tránh việc đó bằng một quy tắc tham lam thông minh.
Thuật toán, kể bằng lời
- Ghi khoảng cách tạm của S là 0, mọi điểm khác là "vô cực".
- Trong các điểm chưa chốt, chọn điểm có khoảng cách tạm nhỏ nhất. Chốt điểm đó: khoảng cách của nó giờ là chính thức.
- Với mỗi láng giềng của điểm vừa chốt: nếu đi qua điểm vừa chốt mà tới láng giềng ngắn hơn khoảng cách tạm hiện có, cập nhật khoảng cách tạm, và ghi nhớ "đến từ đâu".
- Lặp lại bước 2–3 cho đến khi chốt được đích T (hoặc chốt hết mọi điểm).
- Lần ngược theo ghi chú "đến từ đâu" từ T về S để ra đường đi.
Vì sao điểm được chốt là đúng? Vì mọi đường khác tới nó đều phải đi qua một điểm chưa chốt, mà điểm chưa chốt nào cũng đã xa ít nhất bằng nó — cộng thêm đoạn đường dương chỉ càng dài hơn.
Ví dụ với năm điểm
Giả sử từ nhà (S) đến trường (T), có các ngã tư A, B, C. Thời gian đi (phút): S–A 4, S–B 2, B–A 1, A–C 5, B–C 8, C–T 3, A–T 10.
| Bước | Chốt | A | B | C | T |
|---|---|---|---|---|---|
| Khởi đầu | S = 0 | 4 | 2 | ∞ | ∞ |
| 1 | B = 2 | 3 (qua B) | — | 10 | ∞ |
| 2 | A = 3 | — | — | 8 (qua A) | 13 |
| 3 | C = 8 | — | — | — | 11 (qua C) |
| 4 | T = 11 | — | — | — | — |
Đường ngắn nhất: S → B → A → C → T, mất 11 phút. Để ý: đường "trông có vẻ thẳng" S → A → T mất 14 phút, còn đường đi vòng qua B lại nhanh hơn — đúng thứ mà mắt thường hay bỏ sót.
Từ Dijkstra đến bản đồ dẫn đường
Một thành phố lớn có hàng trăm nghìn giao lộ. Chạy Dijkstra nguyên bản trên mạng đường cả nước cho mỗi lần tìm đường là quá chậm. Các hệ thống dẫn đường hiện đại dùng nhiều cải tiến dựa trên cùng ý tưởng:
- Thuật toán A* (1968): giống Dijkstra nhưng ưu tiên điểm vừa gần S vừa có vẻ hướng về T, dựa trên khoảng cách đường chim bay. Loang theo hình "giọt nước" về phía đích thay vì hình tròn.
- Tìm từ hai đầu: loang đồng thời từ S và T, gặp nhau ở giữa.
- Tính trước: chia bản đồ thành tầng — đường phố, đường tỉnh, cao tốc — và tính sẵn các đường tắt giữa các nút quan trọng.
- Trọng số thay đổi: thời gian đi mỗi đoạn được cập nhật theo tình hình giao thông, giờ cao điểm, đường cấm.
Các công ty không công bố hết chi tiết thuật toán, nhưng nguyên tắc nền — chốt dần điểm gần nhất, cập nhật láng giềng — vẫn là của Dijkstra.
Không chỉ là đường xá
- Mạng internet: một số giao thức định tuyến trong mạng nội bộ của các nhà mạng dùng thuật toán kiểu Dijkstra để chọn đường đi cho gói dữ liệu.
- Robot kho hàng tìm lối giữa các kệ, xe tự hành trong nhà máy tránh vật cản.
- Chuyển tuyến xe buýt: trọng số là thời gian chờ cộng thời gian đi.
- Kế hoạch học tập: mỗi điểm là một mốc kiến thức, cạnh là số giờ học để chuyển từ mốc này sang mốc kia.
Góc nhìn hôm nay: chạy Dijkstra bằng tay
Lấy bản đồ khu phố bạn ở, chọn năm sáu ngã tư quen, ghi thời gian đi bộ ước chừng giữa các ngã tư kề nhau. Làm bảng như ví dụ trên để tìm đường ngắn nhất từ nhà đến chợ. So với đường bạn hay đi — rất có thể bạn đã luôn đi đúng đường ngắn nhất nhờ kinh nghiệm, nhưng cũng có thể bảng sẽ chỉ ra một lối tắt bạn chưa từng thử. Đó là lúc thấy thuật toán không phải thứ xa lạ: nó là cách làm có hệ thống thứ người ta vẫn làm bằng trực giác.
Câu hỏi thường gặp
Thuật toán Dijkstra dùng để làm gì?
Để tìm đường đi ngắn nhất từ một điểm đến các điểm khác trong một mạng có độ dài cạnh không âm, như bản đồ đường, mạng máy tính hay mạng xe buýt.
Dijkstra nghĩ ra thuật toán năm nào?
Edsger Dijkstra nghĩ ra thuật toán năm 1956 ở Amsterdam, theo lời ông kể là trong khoảng hai mươi phút ở một quán cà phê, và công bố năm 1959.
Vì sao Dijkstra không dùng được khi có cạnh âm?
Vì thuật toán chốt điểm gần nhất với giả định mọi đoạn tiếp theo chỉ làm đường dài thêm. Cạnh âm phá giả định đó; khi ấy cần thuật toán khác như Bellman–Ford.
Google Maps có dùng thuật toán Dijkstra không?
Các hệ thống dẫn đường không công bố hết chi tiết, nhưng chúng dựa trên cùng nguyên tắc tìm đường ngắn nhất, với nhiều cải tiến như A*, tìm từ hai đầu và tính trước đường tắt.
Thuật toán A* khác Dijkstra thế nào?
A* ưu tiên những điểm vừa gần điểm xuất phát vừa có vẻ hướng về đích, dựa trên ước lượng như khoảng cách đường chim bay, nên thường tìm ra đích nhanh hơn.