Bài 3 trang 66 Chuyên đề Toán 11 Chân trời sáng tạo

Giải Chuyên đề Toán 11 Bài 3: Bài toán tìm đường đi ngắn nhất - Chân trời sáng tạo

Bài 3 trang 66 Chuyên đề Toán 11: Tìm đường đi ngắn nhất từ đỉnh S đến T trong đồ thị trọng số ở Hình 17.

Lời giải:

– Gán nhãn cho S bằng 0 (tức là, n_S = 0), các đỉnh khác bằng ∞. Khoanh tròn đỉnh A.

– Tại các đỉnh kề với S, gồm A, B, C, D. ta có:

⦁ n_A = n_S + w_SA = 0 + 3 = 3.Vì 3 < ∞ nên ta đổi nhãn của A thành 3.

⦁ n_B = n_S + w_SB = 0 + 6 = 6.Vì 6 < ∞ nên ta đổi nhãn của B thành 6.

⦁ n_C = n_S + w_SC = 0 + 9 = 9.Vì 9 < ∞ nên ta đổi nhãn của C thành 9.

⦁ n_D = n_S + w_SD = 0 + 12 = 12.Vì 12 < ∞ nên ta đổi nhãn của D thành 12.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là A nên ta khoanh tròn đỉnh A (đỉnh gần S nhất, chỉ tính các đỉnh khác S).

– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh A gồm B, T, ta có:

⦁ n_B = n_A + w_AB = 3 + 2 = 5.Vì 5 < 6 (6 là nhãn hiện tại của B) nên ta đổi nhãn của B thành 5.

⦁ n_T = n_A + w_AT = 3 + 15 = 18.Vì 18 < ∞ nên ta đổi nhãn của T thành 18.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là B nên ta khoanh tròn đỉnh B (đỉnh gần S thứ hai).

– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh B chỉ có đỉnh C, ta có:

n_C = n_B + w_BC = 5 + 3 = 8.Vì 8 < 9 (9 là nhãn hiện tại của C) nên ta đổi nhãn của C thành 8.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là đỉnh C nên ta khoanh tròn đỉnh C (đỉnh gần S thứ ba).

– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh C gồm D, T, ta có:

⦁ n_D = n_C + w_CD = 8 + 4 = 12.Vì 12 cũng là nhãn hiện tại của D nên ta giữ nguyên nhãn của D là 12.

⦁ n_T = n_C + w_CT = 8 + 5 = 13.Vì 13 < 18 (18 là nhãn hiện tại của T) nên ta đổi nhãn của T thành 13.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là đỉnh D nên ta khoanh tròn đỉnh D (đỉnh gần S thứ tư).

– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh D chỉ còn đỉnh T, ta có:

n_T = n_D + w_DT = 12 + 9 = 21.Vì 21 > 13 (13 là nhãn hiện tại của T) nên ta giữ nguyên nhãn của T là 13.

Lúc này, ta thấy chỉ còn đỉnh T nên ta khoanh tròn đỉnh T (đỉnh gần S thứ năm).

– Nhìn lại các bước trên, ta thấy:

n_T = 13 = n_C + w_CT

= n_B + w_BC + w_CT

= n_A + w_AB + w_BC + w_CT

= n_S + w_SA + w_AB + w_BC + w_CT

= w_SA + w_AB + w_BC + w_CT

= l_SABCT.

Vậy SABCT là đường đi ngắn nhất từ S đến T, với độ dài bằng 13.

Lời giải Chuyên đề Toán 11 Bài 3: Bài toán tìm đường đi ngắn nhất hay, chi tiết khác:

• Khởi động trang 59 Chuyên đề Toán 11: Phần mềm chỉ đường thường chỉ ra đường đi ngắn nhất khi người dùng muốn tìm đường đi ....

• Khám phá 1 trang 59 Chuyên đề Toán 11: Để biểu diễn các con đường nối các giao lộ cùng với độ dài của chúng như sơ đồ ở Hình 1 ....

• Thực hành 1 trang 61 Chuyên đề Toán 11: Cho đồ thị có trọng số như Hình 5. a) Chỉ ra trọng số của các cạnh AE, MN, CN ....

• Khám phá 2 trang 61 Chuyên đề Toán 11: Cho đồ thị có trọng số như Hình 6. a) Tìm tất cả các đường đi từ A đến T (đi qua mỗi đỉnh nhiều nhất một lần) ....

• Thực hành 2 trang 65 Chuyên đề Toán 11: Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh I trong đồ thị có trọng số ở Hình 14 ....

• Vận dụng trang 65 Chuyên đề Toán 11: Trong đồ thị có trọng số ở Hình 15, mỗi cạnh biểu diễn một tuyến xe buýt giữa hai bến trong các bến xe ....

• Bài 1 trang 66 Chuyên đề Toán 11: Cho đồ thị có trọng số như Hình 16. a) Tính độ dài các đường đi ABCD, MBNCP ....

• Bài 2 trang 66 Chuyên đề Toán 11: Bảng 2 cho biết thời gian di chuyển tính bằng giờ của các tuyến xe buýt giữa các bến xe A, B, C, D, E ....

• Bài 4 trang 66 Chuyên đề Toán 11: Tìm đường đi ngắn nhất từ đỉnh A đến P trong đồ thị có trọng số ở Hình 18 ....

• Bài 5 trang 66 Chuyên đề Toán 11: Tìm đường đi ngắn nhất từ đỉnh A đến từng đỉnh (khác A) trong đồ thị có trọng số ở Hình 19 ....

Xem thêm lời giải bài tập Chuyên đề học tập Toán 11 Chân trời sáng tạo hay, chi tiết khác:

• Chuyên đề Toán 11 Bài 2: Đường đi Euler và đường đi Hamilton

• Chuyên đề Toán 11 Bài tập cuối chuyên đề 2

• Chuyên đề Toán 11 Bài 1: Hình biểu diễn của một hình, khối

• Chuyên đề Toán 11 Bài 2: Bản vẽ kĩ thuật

• Chuyên đề Toán 11 Bài tập cuối chuyên đề 3

Xem thêm các tài liệu học tốt lớp 11 hay khác:

• Giải Chuyên đề học tập Toán 11 Kết nối tri thức
• Giải Chuyên đề học tập Toán 11 Chân trời sáng tạo
• Giải Chuyên đề học tập Toán 11 Cánh diều
• Giải lớp 11 Kết nối tri thức (các môn học)
• Giải lớp 11 Chân trời sáng tạo (các môn học)
• Giải lớp 11 Cánh diều (các môn học)

Săn SALE shopee Tết:

• Mỹ phẩm SACE LADY giảm tới 200k
• SRM Simple tặng tẩy trang 50k
• Combo Dầu Gội, Dầu Xả TRESEMME 80k

---