Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng Toán rời rạc 2 - Bài toán tìm đường đi ngắn nhất cung cấp cho người học các kiến thức: Phát biểu bài toán tìm đường đi ngắn nhất, thuật toán Dijkstra, thuật toán Bellman-Ford, thuật toán Floyd. Mời các bạn cùng tham khảo. | Bài giảng Toán rời rạc 2 - Bài toán tìm đường đi ngắn nhất BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc 2 Nội dung Phát biểu bài toán tìm đường đi ngắn nhất Thuật toán Dijkstra Thuật toán Bellman-Ford Thuật toán Floyd 2 Phát biểu bài toán tìm đường đi ngắn nhất Phát biểu bài toán Xét đồ thị G Với mỗi cạnh u v E ta đặt tương ứng với nó một số thực A u v được gọi là trọng số của cạnh. Ta sẽ đặ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ì độ dài của đường đi của nó là. Bài toán dạng tổng quát Tìm đường đi ngắn nhất từ một đỉnh xuất phát s V đỉnh nguồn đến đỉnh cuối t V đỉnh đích . Đường đi như vậy được gọi là đường đi ngắn nhất từ s đến t. Độ dài của đường đi d s t được gọi là khoảng cách ngắn nhất từ s đến t trong trường hợp tổng quát d s t có thể âm . Nếu như không tồn tại đường đi từ s đến t thì độ dài đường đi d s t . 4 Một số thể hiện cụ thể của bài toán Trường hợp 1. Nếu s cố định và t thay đổi Tìm đường đi ngắn nhất từ s đến tất cả các đỉnh còn lại trên đồ thị. Với đồ thị có trọng số không âm bài toán luôn có lời giải bằng thuật toán Dijkstra. Với đồ thị có trọng số âm nhưng không tồn tại chu trình âm bài toán có lời giải bằng thuật toán Bellman-Ford. Trường hợp đồ thị có chu trình âm bài toán không có lời giải. Trường hợp 2. Nếu s thay đổi và t cũng thay đổi Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị. Bài toán luôn có lời giải trên đồ thị không có chu trình âm. Với đồ thị có trọng số không âm bài toán được giải quyết bằng cách thực hiện lặp lại n lần thuật toán Dijkstra. Với đồ thị không có chu trình âm bài toán có thể giải quyết bằng thuật toán Floyd. 5 Thuật toán Dijkstra Mô tả thuật toán Mục đích Sử dụng để tìm đường đi ngắn nhất từ một đỉnh s tới các đỉnh còn lại của đồ thị Áp dụng cho đồ thị có hướng với trọng số không âm. Tư tưởng Gán nhãn tạm thời cho các đỉnh Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất tới đỉnh đó Các nhãn này sẽ được biến đổi tính lại nhờ một thủ tục lặp Ở mỗi một bước lặp
