Tiểu Luận Niên Luận 1: Giải thuật tìm đường đi ngắn nhất Dijkstra (Bài báo cáo kèm demo chương trình)

Chương trình demo có vẽ hình bằng lập trình đồ họa khi tìm đường

MỤC LỤC

LỜI NÓI ĐẦU 6
Chương I: GIỚI THIỆU 7
I. GIỚI THIỆU TỔNG QUAN ĐỀ TÀI 7
I.1. Tổng quan về bài toán đường đi ngắn nhất 7
I.1.1 Phát biểu bài toán 7
I.1.2.Thuật toán Dijkstra 7
II.CÁC MỤC TIÊU CẦN ĐẠT 7
III. KẾ HOẠCH THỰC HIỆN 8
Chương II: MỘT SỐ KHÁI NIỆM TRONG ĐỀ TÀI 9
I. KHÁI NIỆM VỀ ĐỒ THỊ 9
II.BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 11
II.1.Ma trận liền kề ( Ma trận kề ) 11
II.2.Danh sách cạnh 13
III.CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 14
III.1Thuật toán tìm kiếm theo chiều sâu(Depth First Search) 14
III.2 Thuật toán tìm kiếm theo chiều rộng(Breadth First Search) 15
III.3.Độ phức tạp tính toán của DFS và BFS 16
IV. TÍNH LIÊN THÔNG CỦA ĐỒ THỊ 16
IV.1.Định Nghĩa 16
IV1.2.Đối với đồ thị vô hướng G=(V,E) 16
IV.1.3.Đối với đồ thị có hướng G=(V,E) 17
IV.2Tính liên thông trong đồ thị vô hướng 18
V.CÁC THAO TÁC CƠ BẢN VỀ ĐỒ HOẠ 19
V.1.Khái niệm về đồ hoạ 19
V.1.2.Khởi động hệ thống đồ hoạ 20
V.1.3.Lỗi đồ hoạ 22
V.1.4.Mẫu và màu 22
V.1.5.Vẽ 22
Chương III: ỨNG DỤNG THUẬT TOÁN DIJKSTRA GIẢI QUYẾT BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 23
I.Thuật toán Dijkstra 23
II.Lưu đồ thuật toán Dijkstra 24
III.MỘT SỐ HÀM CON 25
III.1Hàm nhập ma trận 25
III.2.Hàm xuất ma trận 25
III.3.Hàm khởi tạo ma trận 26
III.4.Hàm thêm cung 26
III.5.Hàm xoá cung 26
IV.HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH DEMO 26 CHƯƠNG IV: KẾT LUẬN 29 I.KẾT QUẢ ĐẠT ĐƯỢC 29
II.HẠN CHẾ 29
III.HƯỚNG KHẮC PHỤC VÀ PHÁT TRIỂN 29
TÀI LIỆU THAM KHẢO


LỜI NÓI ĐẦU
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đờivà có nhiều ứng dụng hiện đại.Những tư tưởng cơ bản của lý thuyết đồ thị đươc đề xuất từ những năm đầu của thế kỷ 18 bởi nhà toán học người Thụy Sĩ Leonhard Euler.Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thàng phố Konigsberg.
Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau .Chẳng hạn , đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện.Chúng ta có thể phân biệt các hợp chất hoá học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị.Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin được với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán như : tìm đường đi ngắn nhất giữa hai thành phố trong cùng một mạng giao thông . Chúng ta còn sử dụng đồ thị để giải các bài toán về lập lịch,thời khoá biểu,và phân bố tần số cho các trạm phát thanh và truyền hình
Mục đích ta tìm hiểu là nhằm giới thiệu các khái niệm cơ bản,về đồ thị có hướng và đồ thị vô hướng,các cách biểu diễn đồ thị,các phương pháp tìm kiếm trên đồ thị(tìm theo chiều rộng và chiều sâu)và tính liên thông,các giải thuật có liên quan về đồ thị và vận dụng giải thuật điển hình Dijkstra để tìm đường đi ngắn nhất trên đồ thị có hướng, bên cạnh đó là giới thiệu một số thao tác cơ bản về đồ hoạ.