Giải Bài 2.16 trang 49 Chuyên đề Toán 11
Đề bài
Tìm đường đi ngắn nhất từ đỉnh đến mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.
Hình 2.34: Đồ thị có trọng số gồm các đỉnh S, A, D, B, E, C, F. Các cạnh và trọng số: S–A = 2; S–B = 1; S–C = 7; A–D = 5; A–B = 6; A–E = 12 (hoặc cạnh chéo); D–E = 2; B–E = 15; B–F = 10; B–C = 5; C–F = 14; E–F = 6; C–E = 9; và cạnh A–E = 8. Các số ghi trên hình: S–A = 2, S–B = 1, S–C = 7, A–D = 5, A–B = 6, D–E = 2, B–E = 15, đường chéo = 8, B–C = 5, C–F = 14, E–F = 6, B–F = 10, C–E = 9, D–... = 12.
Lời giải
Ta dùng thuật toán Dijkstra (thuật toán gán nhãn) để tìm đường đi ngắn nhất từ đỉnh đến mọi đỉnh còn lại.
Ý tưởng: Mỗi đỉnh được gán một *nhãn tạm thời* là độ dài đường đi ngắn nhất tạm tính từ . Ở mỗi bước, ta chọn đỉnh có nhãn tạm nhỏ nhất để cố định (nhãn đó trở thành chính thức), rồi dùng nó để cập nhật nhãn của các đỉnh kề.
Trọng số các cạnh (theo Hình 2.34):
a) Tiến hành gán nhãn (ô ghi nhãn tạm hiện hành; dấu đánh dấu đỉnh vừa được cố định ở bước đó):
| Bước (cố định) | | | | | | | |
|---|---|---|---|---|---|---|---|
| Khởi tạo | | | | | | | |
| Cố định | | | | | | | |
| Cố định | | | | | | | |
| Cố định | | | | | | | |
| Cố định | | | | | | | |
| Cố định | | | | | | | |
| Cố định | | | | | | | |
| Cố định | | | | | | | |
Giải thích các lần cập nhật chính:
- Cố định : ; ; .
- Cố định : ; .
- Cố định : .
- Cố định : qua là nên giữ nguyên .
b) Kết quả — độ dài đường đi ngắn nhất từ và đường đi tương ứng (truy ngược theo đỉnh đã cố định):
| Đỉnh | Độ dài ngắn nhất | Đường đi |
|---|---|---|
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
Kiểm tra lại: ✓; ✓; ✓. Các đáp số hợp lí.
Đá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.