Giải thuật tìm đường đi ngắn nhất Dijkstra - pdf 17

Chương trình demo có vẽ hình bằng lập trình đồ họa khi tìm đường
Tải miễn phí
Báo cáo niên luận tốt nghiệp tìm đường đi ngắn nhất bằng thuật toán Dijkstra
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ạ.


Link download cho anh em:
IRtVh2M2x6VgPIQ
Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status