Tìm đường đi ngắn nhất từ đỉnh A đến P trong đồ thị ở hình
Tìm đường đi ngắn nhất từ đỉnh A đến P trong đồ thị ở hình sau:
Đáp án đúng là: C
Quảng cáo
Gắn nhãn và tính quãng đường đi của các đỉnh trên đồ thị
- 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.
Đáp án cần chọn là: C
Group 2K9 ôn Thi ĐGNL & ĐGTD Miễn Phí
>> Học trực tuyến Lớp 11 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. Cam kết giúp học sinh lớp 11 học tốt, hoàn trả học phí nếu học không hiệu quả.
 |
 |
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
