Bài 4 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 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.

Lời giải:

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

– Tại các đỉnh kề với đỉnh A, gồm M, N, B, ta có:

⦁ n_M = n_A + w_AM = 0 + 9 = 9.Vì 9 < ∞ nên ta đổi nhãn của M thành 9.

⦁ n_N = n_A + w_AN = 0 + 5 = 5.Vì 5 < ∞ nên ta đổi nhãn của N thành 5.

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

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 A nhất, chỉ tính các đỉnh khác A).

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

⦁ n_M = n_B + w_BM = 3 + 4 = 7.Vì 7 < 9 (9 là nhãn hiện tại của M) nên ta đổi nhãn của M thành 7.

⦁ n_N = n_B + w_BN = 3 + 10 = 13.Vì 13 > 5 (5 là nhãn hiện tại của N) nên ta giữ nguyên nhãn của N là 5.

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

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

⦁ n_M = n_N + w_NM = 5 + 2 = 7.Vì 7 cũng là nhãn hiện tại của M nên ta giữ nguyên nhãn của M là 7.

⦁ n_C = n_N + w_NC = 5 + 6 = 11.Vì 11 < ∞ nên ta đổi nhãn của C thành 11.

⦁ n_P = n_N + w_NP = 5 + 12 = 17.Vì 17 < ∞ nên ta đổi nhãn của P thành 17.

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

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

⦁ n_D = n_M + w_MD = 7 + 10 = 17.Vì 17 < ∞ nên ta đổi nhãn của D thành 17.

⦁ n_P = n_M + w_MP = 7 + 11 = 18.Vì 18 > 17 (17 là nhãn hiện tại của P) nên ta giữ nguyên nhãn của P là 17.

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

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

n_P = n_C + w_CP = 11 + 5 = 16.Vì 16 < 17 (17 là nhãn hiện tại của P) nên ta đổi nhãn của P thành 16.

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

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

n_P = 16 = n_C + w_CP

= n_N + w_NC + w_CP

= n_A + w_AN + w_NC + w_CP

= w_AN + w_NC + w_CP

= l_ANCP.

Vậy ANCP là đường đi ngắn nhất từ đỉnh A đến P, với độ dài bằng 16.

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 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 ....

• 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

---