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 B đến

Câu hỏi số 664438:
Thông hiểu

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

Quảng cáo

Xem lời giải
Câu hỏi:664438
Phương pháp giải

Dùng thuật toán Dijkstra

Giải chi tiết

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

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

Bước 2: Từ D đi đến được A, C, E. Tại A vẫn giữ nhãn 4, tại C vẫn giữ nhãn 5, tại E sửa nhãn 8.

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

Bước 3: Từ A đi đến được C, E. Tại C vẫn giữ nhãn 5, tại E vẫn giữ nhãn 8. Ta khoanh C.

Bước 4: Từ C đi được đến E. Tại E ta gạch nhãn 8 sửa thành 7. Khoanh C là điểm cuối.

Vậy đường đi ngắn nhất là BCE với độ dài bằng 7

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.

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