tailieunhanh - 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à .