Tel: 024.7300.7989 - Phone: 1800.6947 (Thời gian hỗ trợ từ 7h đến 22h)

Giỏ hàng của tôi
Trang chủ
Toán11

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

>> Học trực tuyến Lớp 11 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. Cam kết giúp học sinh lớp 11 học tốt, hoàn trả học phí nếu học không hiệu quả.

Hỗ trợ - Hướng dẫn

  • 024.7300.7989
  • 1800.6947 free

(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com

Đăng ký nhận tư vấn