Tiểu Luận Bài toán Tìm đường di ngắn nhất và ứng dụng

MỤC LỤC
CHƯƠNG 1: ĐẠI CƯƠNG VỀ ĐỒ THỊ. 3
1.1.Đồ thị vô hướng và đồ thị có hướng. 3
1.2.Nửa bậc vào, nửa bậc ra: 4
1.3.Đường đi, chu trình, tính liên thông. 6
CHƯƠNG 2: BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 8
2.1.Giới thiệu bài toán. 8
2.2.Phát biểu bài toán. 9
2.3. Thuật toán Dijkstra. 9
2.4.Thuật toán Bellman - Ford. 15
2.5. Thuật toán Floyd. 18
CHƯƠNG 3: ỨNG DỤNG 29



GIỚI THIỆU

Cùng với sự phát triển nhanh chóng của công nghệ thông tin, lý thuyết đồ thị đã trở thành lĩnh vực toán học quan trọng và cần thiết cho nhiều lĩnh vực khoa học và ứng dụng.
Bài toán tìm đường đi ngắn nhất có nhiều ứng dụng trong thực tế như để tìm đường đi ngắn nhất từ địa điểm này đến địa điểm kia, tìm phương án xây dựng tuyến đường ống dẫn dầu, mạng lưới truyền hình cáp, tuyến bay Những ứng dụng này của bài toán đem lại nhiều lợi ích về kinh tế. Vì vậy chúng em chọn đề tài này.
Trong đề tài này chúng em sẽ trình bày đề tài “ Bài toán Tìm đường di ngắn nhất và ứng dụng ” . Chúng em sẽ trình bày một số thuật toán tìm đường đi ngắn nhất và ứng dụng của nó giải các bài toán thực tế.
Trên cơ sở kiến thức đã học và tham khảo một số tài liệu mà nội dung liên quan đến tiểu luận, cùng với sự gợi ý của thầy, em đã chọn lọc, bổ sung, hệ thống các vấn đề.
Trong tiểu luận, phần nội dung được trình bày theo 3 chương:
Chương1: Đại cương về đồ thị.
Chương 2: Bài toán tìm đường đi ngắn nhất.
Chương 3: Ứng dụng.