Lý thuyết ñồ thị là ngành khoa học ñược phát triển từ lâu nhưng lại có nhiều ứng dụng hiện ñại, nó là kiến thức cơ sở cho nhiều ngành khoa học kỹ thuật khác nhau như Điện tử, Hóa học, Ngôn ngữhọc, Kinh tếhọc, Máy tính, . Nhiều khái niệm của lý thuyết ñồthị ñược sinh ra từcác vấn ñề thực tiễn như: ñường ñi, chu trình, tập ổn ñịnh, chu số, sắc số, duyệt ñồ thị, ñường ñi Hamilton, tâm ñồ thị, luồng vận tải, ñồ thị phẳng, cây bao trùm, cây biểu thức, cây mã tiền tốtối ưu,. vì vậy lý thuyết ñồthị ñã gắn kết nhiều ngành khoa học lại với nhau. Các thuật toán ngắn gọn và lí thú của lý thuyết ñồ thị ñã giúp chúng ta giải quyết rất nhiều bài toán phức tạp trong thực tế, trong ñó vấn ñềtìm ñường ñi ngắn nhất giúp chúng ta giải quyết ñược rất nhiều bài toán trong thực tế. Vì vậy, tôi ñã chọn ñề tài: “Bài toán tìm ñường ñi ngắn nhất và ứng dụng” ñểnghiên cứu.