Tổng quan
Dijkstra's Algorithm tìm đường đi ngắn nhất từ nút xuất phát tới mọi nút khác trong đồ thị có trọng số cạnh không âm. Nó luôn mở rộng nút chưa thăm có khoảng cách đã biết nhỏ nhất, dần chốt lại các khoảng cách tối ưu lan ra từ điểm xuất phát.
Nó tổng quát hóa BFS cho đồ thị có trọng số bằng cách dùng hàng đợi ưu tiên xếp theo khoảng cách tích lũy thay cho hàng đợi FIFO thuần, nên xử lý đúng địa hình có chi phí di chuyển khác nhau.
Thuật toán Dijkstra hoạt động thế nào?
- Đặt khoảng cách của điểm xuất phát bằng 0 và mọi nút khác bằng vô cực.
- Lấy từ hàng đợi ưu tiên nút chưa thăm có khoảng cách nhỏ nhất.
- Nới lỏng từng hàng xóm: nếu đi qua nút hiện tại ngắn hơn thì cập nhật khoảng cách và nút cha của hàng xóm.
- Đánh dấu nút hiện tại đã hoàn tất và lặp lại đến khi đích được chốt, rồi lần theo các nút cha để dựng đường đi.
Khi nào nên dùng?
- Tìm lộ trình ngắn nhất trên đồ thị có trọng số như mạng đường bộ hoặc lưới có chi phí địa hình.
- Định tuyến mạng, khi độ trễ hoặc chi phí liên kết khác nhau giữa các chặng.
- Hãy dùng A* khi có một heuristic tốt để hướng tìm kiếm tới một đích duy nhất nhanh hơn.
Phân tích độ phức tạp
Với hàng đợi ưu tiên bằng heap nhị phân, Dijkstra chạy trong O((V + E) log V): mỗi cạnh có thể kích hoạt một lần cập nhật heap và mỗi đỉnh được lấy ra một lần. Bộ nhớ là O(V) cho khoảng cách và hàng đợi. Vì chỉ nới lỏng với trọng số không âm, nó không bao giờ thăm lại nút đã chốt — nhưng cũng không xử lý được cạnh âm.
Câu hỏi thường gặp
Vì sao Dijkstra không xử lý được trọng số cạnh âm?
Nó giả định rằng một khi nút đã được chốt với khoảng cách nhỏ nhất thì không đường đi nào sau đó cải thiện được nữa. Một cạnh âm có thể khiến lộ trình trông dài hơn lại rẻ hơn về sau, phá vỡ giả định đó — hãy dùng Bellman-Ford cho trọng số âm.
Dijkstra liên hệ thế nào với BFS và A*?
Dijkstra là BFS mở rộng cho đồ thị có trọng số nhờ hàng đợi ưu tiên, còn A* là Dijkstra cộng thêm một ước lượng heuristic cho khoảng cách còn lại. Với heuristic bằng 0, A* hoạt động y hệt Dijkstra.