Tìm đường đi ngắn nhất từ đỉnh X đến đỉnh Y của đồ thị cho trong hình
Tìm đường đi ngắn nhất từ đỉnh X đến đỉnh Y của đồ thị cho trong hình sau:
Quảng cáo
Đặt tên các đỉnh A,B,C,D,E,M như hình vẽ
Gán nhãn tại X bằng 0, các đỉnh còn lại bằng \(\infty \)
Tại các đỉnh A, M, D kề A ta gạch \(\infty \) và thay thế lần lượt bằng 7, 4, 3. Tại D có nhãn bé nhất nên khoanh D.
Tại các đỉnh C, E kề D ta gạch \(\infty \) và lần lượt thay thế bằng 11, 7. Tại các đỉnh chưa khoanh ta thấy M có nhãn bé nhất bằng 4 nên khoanh M.
Tại C kề M gạch 11 thay thế bằng 6. Tại các đỉnh chưa khoanh ta thấy C có nhãn bé nhất bằng 6 nên khoanh C.
Từ C kề các đỉnh A, B. Tại A ta giữ nguyên nhãn 7 (do 7 < 11). Tại B ta gạch \(\infty \) và thay thế bằng 10. Tại các đỉnh chưa khoanh ta thấy A và E có nhãn bằng nhau bằng 7.
Xét tại A đến B ta thấy B vẫn có nhãn là 11 nên giữ nguyên 10 tại B. Từ B đến Y ta được Y nhãn bằng 11.
Xét tai E đến Y ta được Y có nhãn bằng 12 < 11 nên đường đi ngắn nhất là AMCBY.
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
