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

• Toán học
• Bài giảng Lý thuyết đồ thị
• Lý thuyết đồ thị
• Bài toán đường đi ngắn nhất
• Thuật toán Ford
• Thuật toán Dijsktra
• Thuật toán Floyd
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Lịch sử của lý thuyết đồ thị
• Ưng dụng của đồ thị
• Tổng quan lý thuyết đồ thị
• Bài toán 7 cái cầu
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Công thức Euler
• Định lý Kuratowski
• Đồ thị không phẳng
• Tô màu đồ thị
• Bài toán lý thuyết đồ thi
• Bài toán lý thuyết đồ thị
• Bất đẳng thức EV
• Biểu diễn đồ thị
• Bậc của đỉnh
• Định nghĩa đồ thị
• Bài tập đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Đồ thị Haminton
• Cây khung của đồ thị
• Đồ thị đẳng cấu
• Đồ thị tổng vành; Đồ thị đơn giản
• Đồ thị liên thông
• Dạng đồ thị đặc biệt
• Chu trình của đồ thị
• Chiều sâu trên đồ thị
• Chiều rộng trên đồ thị
• Tìm kiếm chiều rộng trên đồ thị
• Tìm kiếm trên đồ thị
• Đồ thị hữu hạn
• Đẳng cấu đồ thị
• Các dạng đồ thị
• Toán ứng dụng