Cho đồ thị sau. Hãy tìm đường ngắn nhất từ đỉnh A đến

Câu hỏi số 664439:

Thông hiểu

Cho đồ thị sau. Hãy tìm đường ngắn nhất từ đỉnh A đến H.

Quảng cáo

Xem lời giải

Câu hỏi:664439

Phương pháp giải

Dùng thuật toán Dijkstra

Giải chi tiết

Bước 0: Khoanh đỉnh A, các đỉnh còn lại chọn nhãn \(\infty \).

Bước 1: Tại đỉnh B sửa nhãn 8, tại C sửa nhãn 12, tại D sửa nhãn 6. Ta thấy D có nhãn nhỏ nhất nên khoanh D.

Bước 2: Từ D đi đến được C, F, H. Tại C ta sửa nhãn 11, tại F sửa nhãn 14, tại H sửa nhãn 19.

Ta thấy trong các điểm chưa khoanh thấy B có nhãn nhỏ nhất nên khoanh B.

Bước 3: Từ B đi đến được C, E. Tại C vẫn giữ nhãn 11, tại E sửa nhãn 13. Ta khoanh C.

Bước 4: Từ C đi được đến E, F. Tại E ta giữ nhãn 13. Tại F vẫn giữ nhãn 14. Khoanh E.

Bước 5: Từ E đi được F, G. Tại F ta vẫn giữ nhãn 14, tại G ta sửa nhãn thành 16. Khoanh F.

Bước 6: Tại F đi được đến H. Tại H ta gạch 19 thay bằng 18. Khoanh H. Kết thúc thuật toán.

Vậy đường đi ngắn nhất bằng 18 và đi qua cá điểm ADFH.

Group 2K9 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòngTD - Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.