Động lực

Dijkstra mở rộng một tập hợp các đỉnh có khoảng cách ngắn nhất đã được xác định. Thuật toán luôn chốt đỉnh chưa được chốt có khoảng cách gần nhất, rồi dùng đỉnh đó để cải thiện (thư giãn) khoảng cách đến các đỉnh kề.

Tại sao nên học Dijkstra?

• Ứng dụng rộng rãi: tìm đường bằng GPS, định tuyến gói tin mạng và mọi bài toán tìm đường đi có chi phí thấp nhất.
• Tham lam nhưng hiệu quả: một ví dụ rõ ràng về lựa chọn tham lam được chứng minh là cho kết quả tối ưu, miễn là trọng số không âm.
• Nền tảng: ý tưởng thư giãn của thuật toán xuất hiện lại trong A* và các thuật toán tìm đường đi ngắn nhất khác.

Quan trọng: Dijkstra giả định không có trọng số âm. Với cạnh âm, cần dùng Bellman-Ford, nội dung của khóa học tiếp theo.