TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị - Bài 7+8: Bài toán đường đi ngắn nhất

Bài giảng "Lý thuyết đồ thị - Bài 7+8: Bài toán đường đi ngắn nhất" cung cấp cho người học các kiến thức: Các khái niệm mở đầu, đường đi ngắn nhất xuất phát từ 1 đỉnh, thuật toán Ford – Bellman, thuật toán Dijsktra, thuật toán Floyd,. . | Bài giảng Lý thuyết đồ thị - Bài 7+8: Bài toán đường đi ngắn nhất Bài 7, 8 Bài toán đường đi ngắn nhất Các khái niệm mở đầu Bài toán: Cho G = là đồ thị có trọng số. s và t là 2 đỉnh của đồ thị. Hãy tìm đường đi có tổng trọng số nhỏ nhất từ s đến t. 20 VD: 5 15 15 3 9 9 5 5 Đường đi ngắn nhất từ Etna đến Oldtown là: Etna – Bangor – Orono – OldTown Đường đi ngắn nhất từ Hermae đến Etna là: Hermae – Hampdea – Bangor - Etna 2 Các khái niệm mở đầu (tt) 1 10 2 5 7 20 9 -6 9 4 3 4 5 Tìm đường đi ngắn nhất từ đỉnh 3 đến đỉnh 5 Trả lời: 3 – 4 – 2 – 5 ??? Độ dài 11 là ngắn nhất ??? Đường đi này thì sao? Độ dài là bao nhiêu? 3–4–2–5–2–5 Đường đi trên đã ngắn nhất chưa??? 3 Các khái niệm mở đầu (tt) Điều kiện để bài toán có lời giải: Phải tồn tại đường đi từ s đến t: Đồ thị vô hướng liên thông Đồ thị có hướng liên thông mạnh Đồ thị vô hướng, s và t nằm trong cùng một thành phần liên thông Đồ thị có hướng, có tồn tại đường đi từ s đến t Trong đồ thị không tồn tại chu trình âm Đồ thị có hướng: không tồn tại chu trình âm. Đồ thị vô hướng: không tồn tại cạnh âm. 5 2 7 1 3 -3 6 2 8 4 1 5 6 4 Đường đi ngắn nhất xuất phát từ 1 đỉnh Nhận xét: Nếu v là đỉnh trung gian trên đường đi ngắn nhất từ s đến t thì đường đi từ s đến v phải là ngắn nhất và đường đi từ v đến t cũng phải là ngắn nhất. s v t X Do đó, để tối ưu, người ta mở rộng bài toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại của đồ thị. 5 Đường đi ngắn nhất xuất phát từ 1 đỉnh (tt) Ý tưởng chung của các thuật toán tìm đường đi ngắn nhất. Dò tìm bằng cách thử đi qua các đỉnh trung gian Nếu phát hiện đường đi qua đỉnh trung gian ngắn hơn đường đi hiện tại thì sẽ cập nhật đường đi mới, đồng thời chỉnh sửa các thông tin liên quan. Sử dụng hai mảng để lưu trữ tạm thời: Mảng d[v]: Lưu trữ độ dài đường đi ngắn nhất hiện tại từ s đến v. Mảng .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.