Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh xuất phát tới mọi đỉnh khác trong đồ thị có trọng số không âm, bằng cách lần lượt chốt đỉnh gần nhất chưa chốt rồi cập nhật khoảng cách tạm thời của các đỉnh kề nó. Edsger Dijkstra, nhà khoa học máy tính người Hà Lan, công bố thuật toán năm 1959, và nó vẫn là nền của nhiều hệ thống tìm đường hiện nay.
Bài chạy tay thuật toán trên một đồ thị năm đỉnh, lập bảng nhãn qua từng vòng để bạn tự làm lại được trên giấy, giải thích vì sao thuật toán đúng, đưa phản ví dụ khi có trọng số âm, nói về độ phức tạp, và cách dùng AI để kiểm bài mà không bị dẫn sai bởi một bảng tính nhầm.
Ý tưởng: lan ra từ điểm xuất phát như vết dầu loang
Hình dung bạn đứng ở đỉnh nguồn, và từ đó một làn sóng lan ra theo các cạnh với tốc độ đều. Đỉnh nào bị sóng chạm tới trước thì gần hơn. Dijkstra mô phỏng đúng hình ảnh đó bằng phép tính: mỗi đỉnh mang một nhãn là khoảng cách ngắn nhất đã biết tới thời điểm hiện tại. Lúc đầu nguồn có nhãn 0, mọi đỉnh khác có nhãn vô cùng.
Mỗi vòng, thuật toán chọn trong các đỉnh chưa chốt đỉnh có nhãn nhỏ nhất và chốt nó, tức là tuyên bố nhãn của nó là khoảng cách ngắn nhất thật sự. Sau đó, với mỗi đỉnh u kề với đỉnh v vừa chốt, nó thử đi vòng qua v: nếu nhãn của v cộng trọng số cạnh v–u nhỏ hơn nhãn hiện tại của u, nhãn của u được giảm xuống, kèm ghi chú rằng u đi tới từ v. Thao tác thử và giảm nhãn này gọi là nới lỏng cạnh.
Thuật toán dừng khi mọi đỉnh đã chốt, hoặc sớm hơn nếu bạn chỉ cần tới một đỉnh đích và đỉnh đích vừa được chốt. Đường đi cụ thể được dựng lại bằng cách lần ngược các ghi chú “đi tới từ đâu”, từ đích về nguồn. Toàn bộ thuật toán chỉ gồm hai thao tác, chọn đỉnh có nhãn nhỏ nhất và nới lỏng cạnh, nhưng phải làm đúng thứ tự thì kết quả mới đúng.
Tính tay trên đồ thị năm đỉnh: bảng nhãn qua từng vòng
Đồ thị vô hướng gồm các đỉnh A, B, C, D, E và các cạnh kèm trọng số: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2. Có thể hiểu trọng số là số phút đi giữa hai điểm, ví dụ giả định. Tìm đường ngắn nhất từ A. Mỗi hàng của bảng là trạng thái nhãn sau khi chốt một đỉnh; dấu sao đánh dấu đỉnh đã chốt.
| Vòng, đỉnh chốt | A | B | C | D | E |
|---|---|---|---|---|---|
| Khởi tạo | 0 | ∞ | ∞ | ∞ | ∞ |
| 1, chốt A | 0* | 4 (từ A) | 2 (từ A) | ∞ | ∞ |
| 2, chốt C | 0* | 3 (từ C) | 2* | 10 (từ C) | 12 (từ C) |
| 3, chốt B | 0* | 3* | 2* | 8 (từ B) | 12 (từ C) |
| 4, chốt D | 0* | 3* | 2* | 8* | 10 (từ D) |
| 5, chốt E | 0* | 3* | 2* | 8* | 10* |
Đọc kết quả: khoảng cách ngắn nhất từ A tới B là 3, tới C là 2, tới D là 8, tới E là 10. Lần ngược ghi chú để dựng đường tới E: E từ D, D từ B, B từ C, C từ A, nên đường là A, C, B, D, E, tổng 2 + 1 + 5 + 2 = 10. Để ý ba lần nhãn bị giảm: B từ 4 xuống 3 nhờ đi vòng qua C, D từ 10 xuống 8 nhờ đi qua B, E từ 12 xuống 10 nhờ đi qua D. Cạnh trực tiếp A–B không nằm trên đường ngắn nhất tới B; đi vòng lại ngắn hơn.
Khi tự làm, mỗi vòng ghi đủ hai việc: đỉnh nào được chốt với nhãn bao nhiêu, và cạnh nào được nới lỏng làm nhãn đổi. Bảng như trên chính là phần trình bày mà giảng viên thường yêu cầu trong bài kiểm tra.
Vì sao chốt đỉnh có nhãn nhỏ nhất là an toàn
Câu hỏi tự nhiên: khi chốt C với nhãn 2 ở vòng hai, sao biết chắc không có đường nào khác tới C ngắn hơn? Lập luận như sau. Mọi đường từ A tới C phải rời khỏi tập các đỉnh đã chốt tại một cạnh nào đó, để đi tới một đỉnh chưa chốt. Nhãn của đỉnh chưa chốt đó không nhỏ hơn nhãn của C, vì C được chọn là nhỏ nhất. Phần đường còn lại từ đỉnh đó tới C có độ dài không âm. Vậy mọi đường khác dài ít nhất bằng nhãn của C.
Mấu chốt của lập luận là cụm “độ dài không âm”. Nếu đồ thị có cạnh trọng số âm, phần đường còn lại có thể làm tổng giảm đi, và lập luận sụp đổ. Đây không phải chi tiết kỹ thuật mà là điều kiện cốt lõi: tính đúng của Dijkstra dựa hoàn toàn vào việc đi thêm không bao giờ làm đường ngắn lại.
Cách nhìn thứ hai, gần với lập trình: Dijkstra là một thuật toán tham lam, mỗi bước chọn phương án tốt nhất tại chỗ và không bao giờ quay lại sửa. Nhiều thuật toán tham lam cho kết quả sai; Dijkstra là trường hợp may mắn mà lựa chọn tham lam được chứng minh là tối ưu, nhưng chỉ trong điều kiện trọng số không âm. Thuộc thuật toán mà không nhớ điều kiện này là cách nhanh nhất để dùng sai nó.
Phản ví dụ với trọng số âm và các thuật toán thay thế
Xét đồ thị có hướng ba đỉnh: A tới B trọng số 2, A tới C trọng số 3, C tới B trọng số −2. Chạy Dijkstra từ A:
- Vòng một chốt A; nhãn B thành 2, nhãn C thành 3.
- Vòng hai chốt B với nhãn 2, vì 2 nhỏ hơn 3.
- Vòng ba chốt C với nhãn 3, thử nới lỏng cạnh C tới B được 3 + (−2) = 1, nhưng B đã chốt nên bản chuẩn của thuật toán không sửa nữa.
- Kết quả Dijkstra nói khoảng cách tới B là 2, trong khi đường A, C, B chỉ dài 1. Sai.
Khi có trọng số âm, dùng thuật toán Bellman–Ford: nới lỏng mọi cạnh, lặp lại n − 1 lần với n là số đỉnh. Chậm hơn Dijkstra nhưng đúng, và còn phát hiện được chu trình âm, trường hợp mà đường ngắn nhất không tồn tại vì cứ đi vòng thì tổng cứ giảm. Ở chiều ngược lại, nếu mọi cạnh có trọng số bằng nhau thì không cần Dijkstra: tìm kiếm theo chiều rộng đã cho đường ít cạnh nhất, đơn giản và nhanh hơn. Trọng số âm hiếm gặp với khoảng cách hay thời gian, nhưng xuất hiện khi trọng số là lợi nhuận, chênh lệch tỷ giá hay mức thay đổi năng lượng.
Một biến thể quen thuộc trong hệ thống tìm đường là thuật toán A* (đọc là A sao), bổ sung cho Dijkstra một ước lượng khoảng cách còn lại tới đích, ví dụ khoảng cách đường chim bay, để ưu tiên các hướng đi về phía đích. Khi ước lượng không bao giờ vượt quá khoảng cách thật, A* vẫn cho đường ngắn nhất mà thường duyệt ít đỉnh hơn.
Độ phức tạp: vì sao cần hàng đợi ưu tiên
Mỗi vòng, thuật toán phải tìm đỉnh chưa chốt có nhãn nhỏ nhất. Cài đặt đơn giản nhất là duyệt hết các đỉnh mỗi vòng, tốn khoảng n bước, lặp n vòng, tổng cỡ n bình phương bước. Với đồ thị một nghìn đỉnh thì khoảng một triệu bước, chấp nhận được. Với đồ thị đường phố một triệu đỉnh, n bình phương là một nghìn tỷ bước, quá chậm.
Cải tiến chuẩn là lưu các đỉnh chưa chốt trong một hàng đợi ưu tiên, thường cài bằng cấu trúc đống nhị phân, cho phép lấy phần tử nhỏ nhất và giảm nhãn một phần tử với chi phí cỡ log n. Tổng chi phí khi đó cỡ (n + m) nhân log n, với m là số cạnh. Đồ thị đường phố thưa, m chỉ gấp vài lần n, nên con số này nhỏ hơn n bình phương rất nhiều. Cách so sánh độ lớn giữa các cách cài đặt được nói kỹ ở bài về ký hiệu Big O trong cùng danh mục.
Các ứng dụng chỉ đường hiện nay xử lý bản đồ lớn hơn nhiều, nên dùng thêm các kỹ thuật như tính trước một phần, chia bản đồ thành vùng, hay A* với ước lượng tốt. Nhưng phần lớn vẫn dựa trên ý tưởng nới lỏng cạnh của Dijkstra. Với người học, hiểu bản gốc chạy tay trên năm đỉnh là bước cần thiết trước khi đọc về những tối ưu đó.
Dùng AI kiểm bài Dijkstra: so từng vòng, không chỉ so đáp số
Bài Dijkstra có thể ra đáp số đúng mà các vòng sai, và giảng viên thường chấm theo bảng từng vòng. Chatbot hay mắc hai lỗi: chốt nhầm đỉnh khi có hai nhãn bằng nhau, và quên rằng đồ thị có hướng. Quy trình kiểm:
- Đưa đồ thị dưới dạng danh sách cạnh, ghi rõ có hướng hay vô hướng, kèm đỉnh nguồn. Không mô tả hình vẽ bằng lời.
- Tự lập bảng nhãn trước. Câu lệnh mẫu: “Đây là bảng nhãn mình lập khi chạy Dijkstra từ A, mỗi dòng một vòng. Chạy lại từng vòng và chỉ ra vòng đầu tiên mà bảng của mình khác bảng của bạn, giải thích vì sao.”
- Khi có hai đỉnh cùng nhãn nhỏ nhất, thống nhất quy tắc chọn, ví dụ theo thứ tự chữ cái, để hai bảng so được với nhau.
- Kiểm đáp số cuối bằng một cách khác: nhờ AI viết đoạn chương trình ngắn chạy Dijkstra trên cùng danh sách cạnh, chạy trên máy của bạn và so kết quả.
- Thử một trường hợp sửa đổi: tăng trọng số một cạnh nằm trên đường ngắn nhất, đoán xem đường có đổi không, rồi chạy lại để kiểm trực giác của mình.
Nếu bạn dùng thuật toán cho dữ liệu thật như tuyến giao hàng của cửa hàng, thay tên khách và địa chỉ bằng mã điểm trước khi đưa vào AI; thuật toán chỉ cần các con số khoảng cách.
Câu hỏi thường gặp
Dijkstra có tìm được đường đi dài nhất không?
Không, và không sửa được đơn giản bằng cách đổi dấu trọng số, vì khi đó các cạnh âm làm thuật toán sai như đã thấy. Bài toán đường đi đơn dài nhất trên đồ thị tổng quát là bài toán khó, chưa có thuật toán hiệu quả. Riêng trên đồ thị có hướng không chu trình thì giải nhanh được bằng quy hoạch động theo thứ tự tô pô.
Đồ thị có hướng và vô hướng chạy Dijkstra có khác nhau không?
Thuật toán giống hệt, chỉ khác ở bước nới lỏng: với đồ thị vô hướng, mỗi cạnh dùng được cả hai chiều; với đồ thị có hướng, chỉ dùng theo chiều mũi tên. Lỗi hay gặp là quên điều này khi chuyển đề bài sang đồ thị, nhất là với bản đồ có đường một chiều.
Dijkstra có tìm đường ngắn nhất giữa mọi cặp đỉnh được không?
Được, bằng cách chạy Dijkstra lần lượt với từng đỉnh làm nguồn. Với đồ thị dày, thuật toán Floyd–Warshall, dùng quy hoạch động với ba vòng lặp lồng nhau, thường gọn hơn khi cài đặt. Lựa chọn giữa hai cách phụ thuộc số đỉnh, số cạnh và việc có trọng số âm hay không.
Vì sao Dijkstra chỉ ra một đường trong khi có thể có nhiều đường cùng ngắn nhất?
Vì thuật toán chỉ giảm nhãn khi tìm được đường ngắn hơn hẳn, không ghi lại các đường bằng nhau. Đường được chọn phụ thuộc thứ tự duyệt. Nếu cần mọi đường ngắn nhất, sửa bước nới lỏng để ghi thêm đỉnh đi tới khi khoảng cách bằng nhau, rồi lần ngược theo mọi nhánh.
Học Dijkstra có cần biết lập trình trước không?
Không bắt buộc. Thuật toán chạy tay trên giấy được với đồ thị nhỏ, và hiểu bản chạy tay là đủ cho phần lớn bài thi toán rời rạc. Biết lập trình giúp bạn kiểm kết quả trên đồ thị lớn và hiểu vì sao cần hàng đợi ưu tiên, nhưng phần tư duy cốt lõi nằm ở bảng nhãn.