Tìm đường đi ngắn nhất từ đỉnh A đến P trong đồ thị có trọng số ở Hình 18
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.
– 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 đỉnh A, gồm M, N, B, ta có:
⦁ nM = nA + wAM = 0 + 9 = 9.Vì 9 < ∞ nên ta đổi nhãn của M thành 9.
⦁ nN = nA + wAN = 0 + 5 = 5.Vì 5 < ∞ nên ta đổi nhãn của N thành 5.
⦁ nB = nA + wAB = 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ó:
⦁ nM = nB + wBM = 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.
⦁ nN = nB + wBN = 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ó:
⦁ nM = nN + wNM = 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.
⦁ nC = nN + wNC = 5 + 6 = 11.Vì 11 < ∞ nên ta đổi nhãn của C thành 11.
⦁ nP = nN + wNP = 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ó:
⦁ nD = nM + wMD = 7 + 10 = 17.Vì 17 < ∞ nên ta đổi nhãn của D thành 17.
⦁ nP = nM + wMP = 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ó:
nP = nC + wCP = 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:
nP = 16 = nC + wCP
= nN + wNC + wCP
= nA + wAN + wNC + wCP
= wAN + wNC + wCP
= lANCP.
Vậy ANCP là đường đi ngắn nhất từ đỉnh A đến P, với độ dài bằng 16.
Xem thêm các bài giải Chuyên đề Toán 11 Chân trời sáng tạo hay, chi tiết khác:
Bài 2: Đường đi Euler và đường đi Hamilton
Bài 3: Bài toán tìm đường đi ngắn nhất