Bài giảng Toán rời rạc: Chương cung cấp cho người học những kiến thức như: Bài toán tìm đường đi ngắn nhất; Giới thiệu bài toán TSP. Mời các bạn cùng tham khảo! | TOÁN RỜI RẠC Chương 6 Đồ thị Giảng viên ThS. Trần Quang Khải Nội dung phần 3 1. Bài toán tìm đường đi ngắn nhất Giải thuật Dijsktra. 2. Giới thiệu bài toán TSP. Toán rời rạc 2011-2012 Chương 6 Đồ thị 2 Chương 6 Bài toán tìm đường đi ngắn nhất Giảng viên ThS. Trần Quang Khải Toán rời rạc 2011-2012 Đồ thị có trọng số Weighted graph Là đồ thị mà mỗi cạnh được gán một số nguyên hoặc thực với ngụ ý nào đó. Toán rời rạc 2011-2012 Chương 6 Đồ thị 4 Đồ thị có trọng số Liên quan Thời gian. Khoảng cách. Chi phí. Toán rời rạc 2011-2012 Chương 6 Đồ thị 5 Đồ thị có trọng số Độ dài length của đường đi có trọng số Tổng trọng số của các cạnh trên đường đi. Đường đi ngắn nhất đường đi có độ dài nhỏ nhất trong số các đường đi có thể có. Lưu ý Khác với khái niệm độ dài là tổng số cạnh. Toán rời rạc 2011-2012 Chương 6 Đồ thị 6 Bài toán tìm đường đi ngắn nhất Shortest path problems Tìm ra đường đi có độ dài nhỏ nhất giữa 2 đỉnh s source và t destination . Các thuật toán Dijsktra giữa 2 đỉnh không cạnh âm . Floyd-Warshall mọi cặp đỉnh . Bellman-Ford có cạnh âm . Toán rời rạc 2011-2012 Chương 6 Đồ thị 7 Bài toán tìm đường đi ngắn nhất Nhận xét Có thể bỏ bớt các cạnh bội chỉ giữ lại cạnh có trọng số nhỏ nhất. Có thể bỏ đi các khuyên có trọng số không âm. Nếu có khuyên trọng số âm có thể không có lời giải. Toán rời rạc 2011-2012 Chương 6 Đồ thị 8 Bài toán tìm đường đi ngắn nhất Biểu diễn đồ thị dạng ma trận kề aij Trọng số cạnh nhỏ nhất nối i đến j nếu có. 0 nếu không có cạnh nối i đến j nếu có. Phải kiểm tra giá trị 0 trong ma trận. Tổng quát hơn thay 0 bằng . Toán rời rạc 2011-2012 Chương 6 Đồ thị 9 Nguyên lý Bellman Gọi P là đường đi ngắn nhất từ i đến j k là một đỉnh nằm giữa i và j trên P thì Đường đi P1 từ i đến k cũng chính là đường đi ngắn nhất từ i đến k. Đường đi P2 từ k đến j cũng chính là đường đi ngắn nhất từ k đến j. Toán rời rạc 2011-2012 Chương 6 Đồ thị 10 Thuật toán Dijsktra Ý tưởng Giải thuật Dijsktra chủ yếu dựa trên nguyên lý gán nhãn labeling . Tác giả Edsger Dijkstra
