Giải Bài 2.15 trang 49 Chuyên đề Toán 11
Đề bài
Tìm đường đi ngắn nhất từ đến trong đồ thị có trọng số trên Hình 2.33.
Hình 2.33: Đồ thị có trọng số gồm 6 đỉnh A, B, C, D, E, F. Các cạnh và trọng số: A–B = 4; A–F = 3; B–C = 11; B–F = 6; B–D (cung cong phía trên) = 20; B–E = 5; C–F = 2; C–E = 10; C–D = 10; F–E = 15; E–B... (cạnh chéo) ; E–D = 7; F–C = 9. Cụ thể các số ghi trên hình: A–B = 4, A–F = 3, B–F = 6, B–C = 11, cung cong A–D = 20, đường chéo B–E = 5, đường chéo C–F = 9, C–E = 2, C–D = 10, F–E = 15, E–D = 7.
Lời giải
Phân tích bài toán. Đồ thị có trọng số gồm 6 đỉnh với các cạnh (lấy theo số ghi trên Hình 2.33):
Ta dùng thuật toán gán nhãn (Dijkstra) để tìm đường đi ngắn nhất từ đến . Mỗi đỉnh được gán một nhãn là độ dài ngắn nhất tạm thời từ tới nó; ở mỗi bước ta chọn đỉnh có nhãn tạm nhỏ nhất để cố định (nhãn chính thức), rồi cập nhật nhãn các đỉnh kề.
Bước 0. Gán nhãn chính thức cho : . Các đỉnh khác nhãn tạm .
Bước 1. Từ cập nhật các đỉnh kề:
Nhãn tạm nhỏ nhất là → cố định .
Bước 2. Từ cập nhật: ; ; với : nên giữ .
Hiện có . Nhỏ nhất là → cố định .
Bước 3. Từ cập nhật: ; với : nên giữ .
Hiện . Nhỏ nhất là → cố định .
Bước 4. Từ cập nhật: ; .
Hiện . Nhỏ nhất là → cố định .
Bước 5. Từ cập nhật : nên giữ . Còn lại chỉ có , cố định với .
Truy vết đường đi. lấy nhãn từ , lấy nhãn từ , lấy nhãn từ . Vậy đường đi ngắn nhất là:
với độ dài .
Kiểm tra lại. So với vài đường khác: ; ; (cung cong trực tiếp). Tất cả đều lớn hơn . Vậy là đường đi ngắn nhất.
Kết luận. Đường đi ngắn nhất từ đến là , độ dài bằng .
Đáp số
Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.