Thực hành 2 trang 65 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

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.

Thực hành 2 trang 65 Chuyên đề học tập Toán 11 Chân trời sáng tạo

Lời giải:

Thực hành 2 trang 65 Chuyên đề học tập Toán 11 Chân trời sáng tạo

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

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

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

⦁ nC = nA + wAC = 0 + 6 = 6.Vì 6 < ∞ nên ta đổi nhãn của C thành 6.

⦁ nD = nA + wAD = 0 + 5 = 5.Vì 5 < ∞ nên ta đổi nhãn của D thành 5.

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

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

⦁ nC = nB + wBC = 3 + 2 = 5.Vì 5 < 6 (6 là nhãn hiện tại của C) nên ta đổi nhãn của C thành 5.

⦁ nE = nB + wBE = 3 + 10 = 13.Vì 13 < ∞ nên ta đổi nhãn của E thành 13.

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

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

⦁ nE = nC + wCE = 5 + 5 = 10.Vì 10 < 13 (13 là nhãn hiện tại của E) nên ta đổi nhãn của E thành 10.

⦁ nD = nC + wCD = 5 + 3 = 8.Vì 8 > 5 (5 là nhãn hiện tại của D) nên ta giữ nguyên nhãn của D là 5.

⦁ nF = nC + wCF = 5 + 6 = 11.Vì 11 < ∞ nên ta đổi nhãn của F thành 11.

⦁ nI = nC + wCI = 5 + 8 = 13.Vì 13 < ∞ nên ta đổi nhãn của I thành 13.

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

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

nF = nD + wDF = 5 + 7 = 12.

Vì 12 > 11 (11 là nhãn hiện tại của F) nên ta giữ nguyên nhãn của F là 11.

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

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

nI = nE + wEI = 10 + 2 = 12.

Vì 12 < 13 (13 là nhãn hiện tại của I) nên ta đổi nhãn của I thành 12.

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

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

nI = nF + wFI = 11 + 4 = 15.

Vì 15 > 12 (12 là nhãn hiện tại của I) nên ta giữ nguyên nhãn của I là 12.

Lúc này, ta thấy chỉ còn đỉnh I chưa được khoanh tròn nên ta khoanh tròn đỉnh I (đỉnh gần A thứ sáu).

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

nI = 12 = nE + wEI

= nC + wCE + wEI

= nB + wBC + wCE + wEI

= nA + wAB + wBC + wCE + wEI

= wAB + wBC + wCE + wEI

= lABCEI.

Vậy ABCEI là đường đi ngắn nhất từ A đến I, với độ dài bằng 12.

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:

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: