Cho đồ thị như hình sau. Tìm các đường đi ngắn nhất từ đỉnh A đến đỉnh
Cho đồ thị như hình sau. Tìm các đường đi ngắn nhất từ đỉnh A đến đỉnh F;
Quảng cáo
Gán nhãn cho A bằng 0, các đỉnh còn lại bằng \(\infty \)
Tại các đỉnh B,C,E ta lần lượt gạch \(\infty \) và thay thế lần lượt là các số 6, 5, 7
Do 5 là số nhỏ nhất nên khoanh tròn C.
Trong các đỉnh chưa khoanh tròn, đỉnh kề với C bao gồm B, D. Tại B ta giữ nguyên nhãn 6 do \(5 + 8 < 6\), tại D gạch nhãn \(\infty \) và thay thế bằng 17. Do tại B có nhãn nhỏ nhất nên khoanh B.
Trong các đỉnh chưa khoanh trong, đỉnh kề với B bao gồm D, F. Tại F ta gạch \(\infty \) và thay thế bằng 14, tại D ta gạch nhãn 17 và thay thế bằng 15.
Nhìn lại các bước trên ta thấy đường đi ABF ngắn nhất.
Group 2K9 ôn Thi ĐGNL & ĐGTD Miễn Phí
>> 2K9 Học trực tuyến - Định hướng luyện thi TN THPT, ĐGNL, ĐGTD ngay từ lớp 11 (Xem ngay) cùng thầy cô giáo giỏi trên Tuyensinh247.com. Bứt phá điểm 9,10 chỉ sau 3 tháng, tiếp cận sớm các kì thi.
 |
 |
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
