Thuật toán Dijkstra

Ứng dụng chỉ đường biết đường nhanh nhất từ cửa nhà bạn đến gần như mọi nơi. Cốt lõi của ý tưởng đó là một thuật toán mà Edsger Dijkstra nghĩ ra trong khoảng hai mươi phút vào năm 1956: lan rộng ra từ điểm xuất phát, và luôn xong nơi gần nhất trước.

Một đồ thị có các cạnh mang độ dài, các đỉnh gần điểm xuất phát đã xong được tô xanh lá, một cây các đường ngắn nhất, và một hàng đợi ưu tiên vẽ bên dưới
Một đồ thị có các cạnh mang độ dài, các đỉnh gần điểm xuất phát đã xong được tô xanh lá, một cây các đường ngắn nhất, và một hàng đợi ưu tiên vẽ bên dưới

Ý tưởng

Hãy hình dung các thị trấn nối với nhau bằng những con đường dài ngắn khác nhau. Câu hỏi là: đường ngắn nhất từ thị trấn của tôi đến mọi thị trấn khác là gì? Tìm kiếm theo chiều rộng trả lời được khi mọi con đường được tính như nhau, nhưng ở đây một lộ trình đi qua nhiều đường hơn có thể lại ngắn hơn. Thuật toán Dijkstra giữ, cho mỗi thị trấn, khoảng cách ngắn nhất tìm được đến lúc đó, và mở rộng một vùng các thị trấn có khoảng cách đã chắc chắn, luôn thêm vào thị trấn gần nhất chưa chắc chắn.

Từng bước

Gán cho điểm xuất phát khoảng cách 0 và mọi đỉnh khác vô cùng. Đưa điểm xuất phát vào hàng đợi ưu tiên, loại hàng đợi luôn trả về đỉnh có khoảng cách nhỏ nhất. Lấy đỉnh đó ra; khoảng cách của nó giờ đã cố định. Với mỗi đỉnh kề chưa cố định, tính khoảng cách đi qua đỉnh này: khoảng cách của nó cộng độ dài cạnh. Nếu kết quả ngắn hơn khoảng cách hiện có của đỉnh kề, hạ khoảng cách xuống, ghi nhớ đỉnh này là đường đến đó, và đưa đỉnh kề vào hàng đợi. Việc này gọi là nới lỏng một cạnh. Lặp lại cho đến khi hàng đợi rỗng, hoặc đến khi đích được lấy ra.

Ví dụ

Lấy các cạnh A–B dài 4, A–C dài 1, B–C dài 2, B–D dài 1, C–D dài 5 và D–E dài 3, và xuất phát từ A. Lấy A ra cho B khoảng cách 4 và C khoảng cách 1. C gần nhất nên được cố định ở 1; qua C, B giảm xuống 1 + 2 = 3 và D nhận 1 + 5 = 6. Giờ B gần nhất, cố định ở 3, và qua B, D giảm xuống 3 + 1 = 4. D cố định ở 4 và cho E 4 + 3 = 7. Vậy đường ngắn nhất từ A đến E là A → C → B → D → E, dài 7, dù A → B → D → E dùng ít cạnh hơn nhưng dài 8.

Vì sao thuật toán đúng

Giả sử đỉnh X là đỉnh gần nhất trong hàng đợi, ở khoảng cách d. Mọi đường khác từ điểm xuất phát đến X đều phải rời vùng các đỉnh đã cố định ở một chỗ nào đó, và đỉnh đầu tiên nó tới bên ngoài vùng đó nằm trong hàng đợi, nên đã cách ít nhất d. Phần đường còn lại không thể làm nó ngắn hơn, vì không có cạnh âm. Vậy d là khoảng cách ngắn nhất đến X. Khi có cạnh âm, lập luận này không còn đúng; khi đó người ta dùng thuật toán Bellman–Ford, thuật toán nới lỏng mọi cạnh hết lần này đến lần khác.

Lịch sử và ứng dụng

Edsger W. Dijkstra thiết kế thuật toán năm 1956 để giới thiệu một máy tính mới, ARMAC ở Amsterdam, bằng cách tìm đường giữa các thành phố Hà Lan, và công bố nó năm 1959. Cùng ý tưởng đó, với một hàng đợi thông minh hơn, chạy trong các ứng dụng chỉ đường và trong các giao thức định tuyến internet như OSPF và IS-IS, vốn tính đường ngắn nhất để dữ liệu đi giữa các bộ định tuyến. Tìm kiếm A* thêm vào một ước lượng khoảng cách còn lại, nên có thể hướng về đích và xét ít đỉnh hơn.

Edsger W. Dijkstra trước bảng đen
Edsger W. Dijkstra trước bảng đen

Khám phá

Mở ứng dụng và nhấn Bước. Số trên các cạnh là độ dài của chúng, và số trên mỗi đỉnh là khoảng cách của nó đến lúc đó. Các đỉnh trong hàng đợi có màu xanh dương, các đỉnh đã cố định màu xanh lá, và hàng đợi dưới đồ thị liệt kê chúng từ gần đến xa, kèm khoảng cách. Hãy để ý những lúc khoảng cách giảm vì một lộ trình trông dài hơn hóa ra lại ngắn hơn, và chọn một đích để thấy quá trình tìm kiếm dừng ngay khi đích được cố định.

Câu hỏi thường gặp

Độ phức tạp thời gian của thuật toán Dijkstra là bao nhiêu?

Tùy vào hàng đợi ưu tiên. Với một danh sách đơn giản là O(V²) với V đỉnh; với đống nhị phân là O((V + E) log V) với E cạnh; với đống Fibonacci là O(E + V log V), như Michael Fredman và Robert Tarjan đã chỉ ra năm 1984.

Thuật toán Dijkstra có xử lý được trọng số cạnh âm không?

Không. Thuật toán giả định rằng khoảng cách của một đỉnh không thể tốt hơn nữa khi đỉnh đó đã gần nhất trong hàng đợi, và một cạnh âm có thể phá vỡ điều đó. Hãy dùng thuật toán Bellman–Ford cho đồ thị có cạnh âm.

Thuật toán Dijkstra có tìm đường đến mọi đỉnh không?

Có. Chạy đến cuối, nó cho khoảng cách ngắn nhất từ điểm xuất phát đến mọi đỉnh tới được, và các đỉnh được ghi nhớ tạo thành một cây đường đi ngắn nhất. Dừng sớm khi đích đã cố định sẽ tiết kiệm công sức nếu chỉ cần một đường đi.

Thuật toán Dijkstra liên quan thế nào đến A*?

Tìm kiếm A* là thuật toán Dijkstra có thêm gợi ý: nó sắp xếp hàng đợi theo khoảng cách hiện có cộng với ước lượng khoảng cách còn lại, chẳng hạn khoảng cách đường chim bay trên bản đồ. Với ước lượng tốt, nó tìm ra cùng đường đi ngắn nhất mà xét ít đỉnh hơn nhiều.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử thuật toán Dijkstra