Bài tập & Lời giải
1. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
Hoạt động: Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.
a) Hãy chỉ ra hai đường đi từ A đến F và so sánh độ dài của hai đường đi đó.
b) Với mỗi đỉnh V của sơ đồ trên Hình 2.28, ta gắn số I(V) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, ta có ngay I(A) = 0. Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn I(B), I(C) của hai đỉnh kề với A là B, C.
Xem lời giải
2. BÀI TOÁN NGƯỜI ĐƯA THƯ
Luyện tập: Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.
Xem lời giải
BÀI TẬP
2.15. Tìm đường đi ngắn nhất từ A đến D trong đồ thị có trọng số trên Hình 2.33.
Xem lời giải
2.16. Tìm đường đi ngắn nhất từ đỉnh S đến mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.
