Giải bài 4 trang 66 Chuyên đề học tập Toán 11 Chân trời sáng tạo

Đề bài

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

Lời giải chi tiết

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

– Tại các đỉnh kề với đỉnh A, gồm M, N, B, ta có:

⦁ \({n_M}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AM}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}9{\rm{ }} = {\rm{ }}9\).Vì \(9{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của M thành 9.

⦁ \({n_N}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AN}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}5{\rm{ }} = {\rm{ }}5\).Vì \(5{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của N thành 5.

⦁ \({n_B}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AB}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}3{\rm{ }} = {\rm{ }}3\).Vì \(3{\rm{ }} < {\rm{ }}\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à 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ó:

⦁ \({n_M}\; = {\rm{ }}{n_B}\; + {\rm{ }}{w_{BM}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}4{\rm{ }} = {\rm{ }}7\).Vì \(7{\rm{ }} < {\rm{ }}9\) (9 là nhãn hiện tại của M) nên ta đổi nhãn của M thành 7.

⦁ \({n_N}\; = {\rm{ }}{n_B}\; + {\rm{ }}{w_{BN}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}10{\rm{ }} = {\rm{ }}13\).Vì \(13{\rm{ }} > {\rm{ }}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ó:

⦁ \({n_M}\; = {\rm{ }}{n_N}\; + {\rm{ }}{w_{NM}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}2{\rm{ }} = {\rm{ }}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.

⦁ \({n_C}\; = {\rm{ }}{n_N}\; + {\rm{ }}{w_{NC}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}6{\rm{ }} = {\rm{ }}11\).Vì \(11{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của C thành 11.

⦁ \({n_P}\; = {\rm{ }}{n_N}\; + {\rm{ }}{w_{NP}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}12{\rm{ }} = {\rm{ }}17\).Vì \(17{\rm{ }} < {\rm{ }}\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à 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ó:

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

⦁ \({n_P}\; = {\rm{ }}{n_M}\; + {\rm{ }}{w_{MP}}\; = {\rm{ }}7{\rm{ }} + {\rm{ }}11{\rm{ }} = {\rm{ }}18\).Vì \(18{\rm{ }} > {\rm{ }}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ó:

\({n_P}\; = {\rm{ }}{n_C}\; + {\rm{ }}{w_{CP}}\; = {\rm{ }}11{\rm{ }} + {\rm{ }}5{\rm{ }} = {\rm{ }}16\).Vì \(16{\rm{ }} < {\rm{ }}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:

\(\begin{array}{*{20}{l}}{{n_P}\; = {\rm{ }}16{\rm{ }} = {\rm{ }}{n_C}\; + {\rm{ }}{w_{CP}}}\\{ = {\rm{ }}{n_N}\; + {\rm{ }}{w_{NC}}\; + {\rm{ }}{w_{CP}}}\\{ = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AN}}\; + {\rm{ }}{w_{NC}}\; + {\rm{ }}{w_{CP}}}\\{ = {\rm{ }}{w_{AN}}\; + {\rm{ }}{w_{NC}}\; + {\rm{ }}{w_{CP}}}\\{ = {\rm{ }}{l_{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.