Tìm đường đi ngắn nhất từ đỉnh A đến P trong đồ thị có trọng số ở hình

Câu hỏi số 664314:

Thông hiểu

Tìm đường đi ngắn nhất từ đỉnh A đến P trong đồ thị có trọng số ở hình sau:

Quảng cáo

Xem lời giải

Câu hỏi:664314

Giải chi tiết

- Gán nhãn cho \({\rm{A}}\) bằng 0 (tức là, \({{\rm{n}}_{\rm{A}}} = 0\) ), các đỉnh khác bằng \(\infty \). Khoanh tròn đỉnh \({\rm{A}}\).

- Tại các đỉnh kề với đỉnh \({\rm{A}}\), gồm \({\rm{M}},{\rm{N}},{\rm{B}}\), ta có:

- \({{\rm{n}}_{\rm{M}}} = {{\rm{n}}_{\rm{A}}} + {{\rm{w}}_{{\rm{AM}}}} = 0 + 9 = 9\).Vì \(9 < \infty \) nên ta đỗi nhãn của \(M\) thành 9 .

- \({{\rm{n}}_{\rm{N}}} = {{\rm{n}}_{\rm{A}}} + {{\rm{w}}_{{\rm{AN}}}} = 0 + 5 = 5\).Vì \(5 < \infty \) nên ta đổi nhãn của \({\rm{N}}\) thành 5 .

- \({{\rm{n}}_{\rm{B}}} = {{\rm{n}}_{\rm{A}}} + {{\rm{w}}_{{\rm{AB}}}} = 0 + 3 = 3\). Vì \(3 < \infty \) 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à \({\rm{B}}\) nên ta khoanh tròn đỉnh \({\rm{B}}\) (đỉnh gần \({\rm{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 \({\rm{B}}\) gồm \({\rm{M}},{\rm{N}}\), ta có:

- \({n_M} = {n_B} + {w_{BM}} = 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

- \({{\rm{n}}_{\rm{N}}} = {{\rm{n}}_{\rm{B}}} + {{\rm{w}}_{{\rm{BN}}}} = 3 + 10 = 13\).Vì \(13 > 5\) (5 là nhãn hiện tại của \({\rm{N}}\) ) nên ta giữ nguyên nhãn của \({\rm{N}}\) là 5 .

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

- Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh \({\rm{N}}\) gồm \({\rm{M}},{\rm{C}},{\rm{P}}\), ta có:

- \({n_M} = {n_N} + {w_{NM}} = 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 .

- \({{\rm{n}}_{\rm{C}}} = {{\rm{n}}_{\rm{N}}} + {{\rm{w}}_{{\rm{NC}}}} = 5 + 6 = 11\). Vì \(11 < \infty \) nên ta đổi nhãn của \({\rm{C}}\) thành 11.

- \({n_P} = {n_N} + {w_{NP}} = 5 + 12 = 17\).Vì \(17 < \infty \) 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à \({\rm{M}}\) nên ta khoanh tròn đỉnh \({\rm{M}}\) (đỉnh gần \({\rm{A}}\) thứ ba).

- Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh \({\rm{M}}\) gồm \({\rm{D}},{\rm{P}}\), ta có:

- \({n_D} = {n_M} + {w_{MD}} = 7 + 10 = 17\).Vì \(17 < \infty \) nên ta đổi nhãn của \(D\) thành 17.

- \({n_P} = {n_M} + {w_{MP}} = 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à \({\rm{C}}\) nên ta khoanh tròn đỉnh \({\rm{C}}\) (đỉnh gần \({\rm{A}}\) thứ tư).

- Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh \({\rm{C}}\) chỉ có đỉnh \({\rm{P}}\), ta có:

\({n_P} = {n_C} + {w_{CP}} = 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 \({\rm{P}}\) nên ta khoanh tròn đỉnh \({\rm{P}}\) (đỉnh gần \({\rm{A}}\) thứ năm).

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

\(\begin{array}{l}{n_P} = 16 = {n_C} + {w_{CP}}\\ = {n_N} + {w_{NC}} + {w_{CP}}\\ = {n_A} + {w_{AN}} + {w_{NC}} + {w_{CP}}\\ = {w_{AN}} + {w_{NC}} + {w_{CP}} = {I_{ANCP}}\end{array}\)

Vậy ANCP là đường đi ngắn nhất từ đỉnh A đến P, với độ dài bằng 16.

Group 2K9 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Học trực tuyến - Định hướng luyện thi TN THPT, ĐGNL, ĐGTD ngay từ lớp 11 (Xem ngay) cùng thầy cô giáo giỏi trên Tuyensinh247.com. Bứt phá điểm 9,10 chỉ sau 3 tháng, tiếp cận sớm các kì thi.