Giải bài 3 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 S đến T trong đồ thị trọng số ở Hình 17.

Lời giải chi tiết

– Gán nhãn cho S bằng 0 (tức là, n_S = 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ó:

⦁ \({n_A}\; = {\rm{ }}{n_S}\; + {\rm{ }}{w_{SA}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}3{\rm{ }} = {\rm{ }}3\).Vì \(3{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của A thành 3.

⦁ \({n_B}\; = {\rm{ }}{n_S}\; + {\rm{ }}{w_{SB}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}6{\rm{ }} = {\rm{ }}6\).Vì \(6{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của B thành 6.

⦁ \({n_C}\; = {\rm{ }}{n_S}\; + {\rm{ }}{w_{SC}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}9{\rm{ }} = {\rm{ }}9\).Vì \(9{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của C thành 9.

⦁ \({n_D}\; = {\rm{ }}{n_S}\; + {\rm{ }}{w_{SD}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}12{\rm{ }} = {\rm{ }}12\).Vì \(12{\rm{ }} < {\rm{ }}\infty \) 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ó:

⦁ \({n_B}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AB}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}2{\rm{ }} = {\rm{ }}5\).Vì \(5{\rm{ }} < {\rm{ }}6\) (6 là nhãn hiện tại của B) nên ta đổi nhãn của B thành 5.

⦁ \({n_T}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AT}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}15{\rm{ }} = {\rm{ }}18\).Vì \(18{\rm{ }} < {\rm{ }}\infty \) 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ó:

\({n_C}\; = {\rm{ }}{n_B}\; + {\rm{ }}{w_{BC}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}3{\rm{ }} = {\rm{ }}8\).Vì \(8{\rm{ }} < {\rm{ }}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ó:

⦁ \({n_D}\; = {\rm{ }}{n_C}\; + {\rm{ }}{w_{CD}}\; = {\rm{ }}8{\rm{ }} + {\rm{ }}4{\rm{ }} = {\rm{ }}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.

⦁ \({n_T}\; = {\rm{ }}{n_C}\; + {\rm{ }}{w_{CT}}\; = {\rm{ }}8{\rm{ }} + {\rm{ }}5{\rm{ }} = {\rm{ }}13\).Vì \(13{\rm{ }} < {\rm{ }}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ó:

\({n_T}\; = {\rm{ }}{n_D}\; + {\rm{ }}{w_{DT}}\; = {\rm{ }}12{\rm{ }} + {\rm{ }}9{\rm{ }} = {\rm{ }}21\).Vì \(21{\rm{ }} > {\rm{ }}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:

\(\begin{array}{*{20}{l}}{{n_T}\; = {\rm{ }}13{\rm{ }} = {\rm{ }}{n_C}\; + {\rm{ }}{w_{CT}}}\\{ = {\rm{ }}{n_B}\; + {\rm{ }}{w_{BC}}\; + {\rm{ }}{w_{CT}}}\\{ = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AB}}\; + {\rm{ }}{w_{BC}}\; + {\rm{ }}{w_{CT}}}\\{ = {\rm{ }}{n_S}\; + {\rm{ }}{w_{SA}}\; + {\rm{ }}{w_{AB}}\; + {\rm{ }}{w_{BC}}\; + {\rm{ }}{w_{CT}}}\\{ = {\rm{ }}{w_{SA}}\; + {\rm{ }}{w_{AB}}\; + {\rm{ }}{w_{BC}}\; + {\rm{ }}{w_{CT}}}\\{ = {\rm{ }}{l_{SABCT}}.}\end{array}\)

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