Câu hỏi:

13/07/2024 4,035

Tìm đường đi ngắn nhất từ đỉnh S đến T trong đồ thị trọng số ở Hình 17.

Tìm đường đi ngắn nhất từ đỉnh S đến T trong đồ thị trọng số ở Hình 17. (ảnh 1)

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack
Tìm đường đi ngắn nhất từ đỉnh S đến T trong đồ thị trọng số ở Hình 17. (ảnh 2)

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

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

nA = nS + wSA = 0 + 3 = 3. Vì 3 < ∞ nên ta đổi nhãn của A thành 3.

nB = nS + wSB = 0 + 6 = 6. Vì 6 < ∞ nên ta đổi nhãn của B thành 6.

nC = nS + wSC = 0 + 9 = 9. Vì 9 < ∞ nên ta đổi nhãn của C thành 9.

nD = nS + wSD = 0 + 12 = 12. Vì 12 < ∞ nên ta đổi nhãn của D thành 12.

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

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

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

nT = nA + wAT = 3 + 15 = 18. Vì 18 < ∞ nên ta đổi nhãn của T thành 18.

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 S thứ hai).

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

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

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

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

nD = nC + wCD = 8 + 4 = 12. Vì 12 cũng là nhãn hiện tại của D nên ta giữ nguyên nhãn của D là 12.

nT = nC + wCT = 8 + 5 = 13. Vì 13 < 18 (18 là nhãn hiện tại của T) nên ta đổi nhãn của T thành 13.

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

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

nT = nD + wDT = 12 + 9 = 21. Vì 21 > 13 (13 là nhãn hiện tại của T) nên ta giữ nguyên nhãn của T là 13.

Lúc này, ta thấy chỉ còn đỉnh T nên ta khoanh tròn đỉnh T (đỉnh gần S thứ năm).

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

nT = 13 = nC + wCT

= nB + wBC + wCT

= nA + wAB + wBC + wCT

= nS + wSA + wAB + wBC + wCT

= wSA + wAB + wBC + wCT

= lSABCT.

Vậy SABCT là đường đi ngắn nhất từ S đến T, với độ dài bằng 13.

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Tìm đường đi ngắn nhất từ đỉnh A đến P trong đồ thị có trọng số ở Hình 18.   (ảnh 2)

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

Lời giải

Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh I trong đồ thị có trọng số ở Hình 14.   (ảnh 2)

– 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

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay