Tìm đường đi ngắn nhất từ đỉnh A đến P trong đồ thị có trọng số ở Hình 18.
Bằng cách nhấp vào Đăng nhập, bạn đồng ý Chính sách bảo mật và Điều khoản sử dụng của chúng tôi. Nếu đây không phải máy tính của bạn, để đảm bảo an toàn, hãy sử dụng Cửa sổ riêng tư (Tab ẩn danh) để đăng nhập (New Private Window / New Incognito Window).
– 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.
Tham gia Cộng đồng Lazi trên các mạng xã hội | |
Fanpage: | https://www.fb.com/lazi.vn |
Group: | https://www.fb.com/groups/lazi.vn |
Kênh FB: | https://m.me/j/AbY8WMG2VhCvgIcB |
LaziGo: | https://go.lazi.vn/join/lazigo |
Discord: | https://discord.gg/4vkBe6wJuU |
Youtube: | https://www.youtube.com/@lazi-vn |
Tiktok: | https://www.tiktok.com/@lazi.vn |
Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi
Vui | Buồn | Bình thường |