Với giải Bài 5 trang 66 Chuyên đề Toán 11 Chân trời sáng tạo chi tiết trong Bài 3: Bài toán tìm đường đi ngắn nhất giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Chuyên đề Toán 11. Mời các bạn đón xem:

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

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.

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 A, gồm E, B, D, F, ta có:

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

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

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

⦁ n_F = n_A + w_AF = 0 + 12 = 12.Vì 12 < ∞ nên ta đổi nhãn của F thành 12.

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

Ta có n_E = 3 = n_A + w_AE = w_AE = l_AE.

Vì vậy AE là đường đi ngắn nhất từ A đến E, với độ dài bằng 3.

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

n_B = n_E + w_EB = 3 + 2 = 5.Vì 5 < 7 (7 là nhãn hiện tại của B) nên ta đổi nhãn của B 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 A thứ hai).

Ta có n_B = 5 = n_E + w_EB = n_A + w_AE + w_EB = w_AE + w_EB = l_AEB.

Vì vậy AEB là đường đi ngắn nhất từ A đến B, với độ dài bằng 5.

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

⦁ n_F = n_B + w_BF = 5 + 8 = 13.Vì 13 > 12 (12 là nhãn hiện tại của F) nên ta giữ nguyên nhãn của F là 12.

⦁ n_C = n_B + w_BC = 5 + 4 = 9.Vì 9 < ∞ nên ta đổi nhãn của C thành 9.

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 A thứ ba).

Ta có n_D = 6 = n_A + w_AD = w_AD = l_AD.

Vì vậy AD là đường đi ngắn nhất từ đỉnh A đến D, với độ dài bằng 6.

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

⦁ n_F = n_D + w_DF = 6 + 5 = 11.Vì 11 < 12 (12 là nhãn hiện tại của F) nên ta đổi nhãn của F thành 11.

⦁ n_C = n_D + w_DC = 6 + 4 = 10.Vì 10 > 9 (9 là nhãn hiện tại của C) nên ta giữ nguyên nhãn của C là 9.

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 A thứ tư).

Ta có n_C = 9 = n_B + w_BC

= n_E + w_EB + w_BC

= n_A + w_AE + w_EB + w_BC

= w_AE + w_EB + w_BC

= l_AEBC.

Vì vậy AEBC là đường đi ngắn nhất từ A đến C, với độ dài bằng 9.

– Lúc này, ta thấy chỉ còn đỉnh F chưa được khoanh tròn nên ta khoanh tròn đỉnh F (đỉnh gần A thứ năm).

Ta có n_F = 11 = n_D + w_DF = n_A + w_AD + w_DF = w_AD + w_DF = l_ADF.

Vì vậy ADF là đường đi ngắn nhất từ A đến F, với độ dài bằng 11.

Vậy đường đi ngắn nhất từ đỉnh A đến các đỉnh B, C, D, E, F lần lượt là AEB, AEBC, AD, AE, ADF.