Thạc Sĩ Các thuật toán tìm đường đi ngắn nhất trong đồ thị lý thuyết, thuật toán và ứng dụng

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

MỤC LỤC
LỜI NÓI ĐẦU 1
Chương I: MỘT SỐ KIẾN THỨC CƠ BẢN TRONG LÝ THUYẾT ĐỒ THỊ 2
1.1 Các khái niệm cơ bản của lý thuyết đồ thị . 2
1.1.1 Định nghĩa đồ thị 2
1.1.2. Các thuật ngữ cơ bản . 5
1.1.3. Định nghĩa đường đi, chu trình, đồ thị liên thông. 7
1.2 Đường đi ngắn nhất 11
1.2.1 Đường đi ngắn nhất xuất phát từ một đỉnh . 11
1.2.2 Đường trong đồ thị không có chu trình 11
1.2.3 Đường đi ngắn nhất giữa hai cặp đỉnh 14
1.3 Một số bài toán dẫn đến bài toán tìm đường đi ngắn nhất trong đồ thị 15
1.3.1 Tìm đường đi ngắn nhất từ điểm A đến điểm B trong thành phố. . 15
1.3.2 Tối ưu hệ thống mạng truyền dẫn. 18
Chương II: ĐƯỜNG ĐI NGẮN NHẤT TỪ MỘT ĐỈNH 21
2.1.Thuật toán Bellman-Ford 27
2.2. Thuật toán Dijkstra . 31
2.3. Thuật toán tìm kiếm A*. . 37
Chương III : ĐƯỜNG ĐI NGẮN NHẤT GIỮA TẤT CẢ CÁC CẶP ĐỈNH 40
3.1. Thuật toán Floyd-Warshall . 48
3.2. Thuật toán Johnson 55
Chương IV: ỨNG DỤNG THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VÀO
MÔ HÌNH HỆ THỐNG ROUTING TĨNH 60
4.1. Nguyên lý hoạt động cơ bản của Router trong hệ thống mạng. . 60
4.2. Ứng dụng một thuật toán (Dijkstra). 69
4.3. Thiết kế chương trình áp dụng thuật toán (Floyd-Warshall). . 71
4.4. Kết quả thử nghiệm 71
TÀI LIỆU THAM KHẢO 73

1

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

LỜI NÓI ĐẦU
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đời và 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 lỗi lạc người Thụy Sĩ Leonhard Euler.
Đồ 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.
Trong đời sống, chúng ta thường gặp các tình huống như sau: để đi từ điểm A
đến điểm B trong thành phố, có nhiều đường đi, nhiều cách đi; có lúc ta chọn đường
đi ngắn nhất (theo nghĩa cự ly), có lúc lại cần trọn đường đi nhanh nhất (theo nghĩa
thời gian),v.v
Mục đích đề tài tìm hiểu, nghiên cứu các thuật toán tìm đường đi ngắn nhất
trong đồ thị phục vụ việc nghiên cứu khoa học và ứng dụng vào thực tiễn.
Củng cố và rèn luyện kỹ năng lập trình, nhớ lại các thuật toán
Chương I : Một số kiến thức cơ bản trong lý thuyết đồ thị.
Chương II : Đường đi ngắn nhất từ một đỉnh.
Chương III : Đường đi ngắn nhất giữa tất cả các cặp đỉnh.
Chương IV : Ứng dụng thuật toán tìm đường đi ngắn nhất vào mô hình
hệ thống routing tĩnh.