TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 5 - Ngô Hữu Phúc

"Bài giảng Lý thuyết đồ thị - Chương 5: Tìm đường đi ngắn nhất" trình bày về giới thiệu về bài toán, thuật toán gán nhãn, thuật toán Dijkstra. | CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT Trong phần này giới thiệu về giải thuật tìm đường đi ngắn nhất giữa 2 đỉnh trên đồ thị có trọng số. Nội dung gồm . Giới thiệu về bài toán . Thuật toán gán nhãn. . Thuật toán Dijkstra 80 CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT . Giới thiệu về bài toán Xét đồ thị G lt V E gt với V n E m. Với mỗi cạnh u v E có một giá trị trọng số A u v . Đặt A u v nếu u v E. Nếu dãy v0 v1 . vk là một đường đi trên G thì ki 1 A vi 1 vi được gọi là độ dài của đường đi. Bài toán Tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t của đồ thị G. 81 CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT . Thuật toán gán nhãn 1 4 Thuật toán được mô tả như sau Từ ma trận trọng số A u v u v V tìm cận trên d v của khoảng cách từ s đến tất cả các đỉnh v V. Nếu thấy d u A u v lt d v thì d v d u A u v làm tốt lên giá trị của d v Quá trình sẽ kết thúc khi không thể làm tốt lên được nữa. Khi đó d v sẽ cho ta giá trị ngắn nhất từ đỉnh s đến đỉnh v. Giá trị d v được gọi là nhãn của đỉnh v. 82 CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT . Thuật toán gán nhãn 2 4 Ví dụ về thuật toán Tìm đường đi ngắn nhất từ A đến Z trong đồ thị G sau. 83 CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT . Thuật toán gán nhãn 3 4 Các bước thực hiện của giải thuật Bước 1 Gán cho nhãn đỉnh A là 0 d A 0 Bước 2 Chọn cạnh có độ dài nhỏ nhất xuất phát từ A cạnh AC gán nhãn của đỉnh kề C với d C d A A A C 0 5 5 84 CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT . Thuật toán gán nhãn 3 4 Bước 3 Tiếp đó trong số các cạnh đi từ một đỉnh có nhãn là A hoặc C tới một đỉnh chưa được gán nhãn chọn cạnh sao cho nhãn của đỉnh với trọng số cạnh tương ứng nhỏ nhất gán cho nhãn của đỉnh cuối của cạnh Như vậy ta lần lượt gán được các nhãn như sau d B 6 vì d B CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT . Thuật toán gán nhãn 4 4 Các bước được mô tả như trong bảng sau Như vậy độ dài đường đi ngắn nhất từ A đến Z là 18. Đường đi ngắn nhất từ A đến Z qua các đỉnh A C D G Z 86 CHƯƠNG V. TÌM ĐƯỜNG ĐI NGẮN NHẤT . Thuật toán Dijkstra 1 6 Thuật toán này do nhà .

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Tìm đường đi ngắn nhất
• Thuật toán gán nhãn
• Thuật toán Dijkstra
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Cây khung của đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Tìm kiếm trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng