tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 8 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 8 Bài toán đường đi ngắn nhất, cung cấp cho người đọc những kiến thức như: Bài toán đường đi ngắn nhất; Đường đi có trọng số bé nhất; Thuật toán Dijsktra; Đường đi trên đồ thị phi chu trình; Đường đi ngắn nhất giữa các cặp đỉnh; Tâm của đồ thị. Mời các bạn cùng tham khảo! | CHƯƠNG 8 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 1 43 NỘI DUNG Bài toán đường đi ngắn nhất Đường đi có trọng số bé nhất Thuật toán Dijsktra Đường đi trên đồ thị phi chu trình Đường đi ngắn nhất giữa các cặp đỉnh Tâm của đồ thị 2 43 . BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Bài toán Cho đồ thị G V E và hai đỉnh a b. Tìm đường đi ngắn nhất nếu có đi từ đỉnh a đến đỉnh b trong đồ thị G. Ý nghĩa thực tế Bài toán giúp chúng ta chọn các hành trình tiết kiệm nhất quãng đường thời gian chi phí . trong giao thông lập lịch thi công công trình một cách tối ưu xử lý trong truyền tin . 3 43 . BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT tiếp Thuật toán duyệt đồ thị theo chiều rộng đã cho ta lời giải của bài toán này. Song ta có thêm thuật toán sau đây. 4 43 TÌM ĐƯỜNG ĐI NGẮN NHẤT 1 Lần lượt gán nhãn cho các đỉnh của đồ thị mỗi đỉnh không quá một lần như sau - Đỉnh a được gán nhãn là số 0. - Những đỉnh kề với đỉnh a được gán số 1. - Những đỉnh kề với đỉnh đã được gán nhãn số 1 được gán số 2. - Tương tự những đỉnh kề với đỉnh đã được gán số i được gán nhãn là số i 1. 5 43 TÌM ĐƯỜNG ĐI NGẮN NHẤT tiếp 2 Thực hiện cho đến khi gán được nhãn cho đỉnh b hoặc không gán nhãn được nữa. Nếu đỉnh b được gán nhãn nào đó là k thì kết luận có đường đi ngắn nhất từ đỉnh a tới đỉnh b với độ dài k ngược lại thì trả lời là không có. 6 43 TÌM ĐƯỜNG ĐI NGẮN NHẤT tiếp Khôi phục đường đi Nếu ở bước 2 chỉ ra b được gán nhãn k nào đó thì ta đi ngược lại theo quy tắc sau đây Nếu đỉnh y được gán nhãn j với j 1 thì sẽ có đỉnh x được gãn nhãn j-1 sao cho có cạnh đi từ x tới y. Đi ngược lại cho đến khi gặp đỉnh a ta nhận được đường đi ngắn nhất cần tìm. 7 43 BÀI TOÁN SÓI DÊ VÀ BẮP CẢI Một con sói một con dê và một cái bắp cải đang ở bờ sông. Người lái đò phải đưa chúng sang sông. Nhưng thuyền quá bé nên mỗi chuyến chỉ chở được một hành khách thôi. Vì những lý do mà ai cũng biết không thể bỏ mặc sói với dê hoặc dê với bắp cải mà không có người trông. Vậy người lái đò phải xử trí thế nào mà vẫn đưa được sói dê và bắp cải sang bên kia sông. 8 .