Giải bài 10 trang 69 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 M đến N trong đồ thị có trọng số sau:

Lời giải chi tiết

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

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

⦁ $n_A=n_M+w_{MA}=0+3=3$.Vì $3<\mathrm{\infty }$ nên ta đổi nhãn của A thành 3.

⦁ $n_B=n_M+w_{MB}=0+4=4$.Vì $4<\mathrm{\infty }$ nên ta đổi nhãn của B thành 4.

⦁ $n_C=n_M+w_{MC}=0+5=5$.Vì $5<\mathrm{\infty }$ nên ta đổi nhãn của C thành 5.

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 M nhất, chỉ tính các điểm khác M).

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

$n_D=n_A+w_{AD}=3+8=11$.Vì $11<\mathrm{\infty }$ nên ta đổi nhãn của D thành 11.

⦁ $n_E=n_A+w_{AE}=3+10=13$.Vì $13<\mathrm{\infty }$ 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à B nên ta khoanh tròn đỉnh B (đỉnh gần M thứ hai).

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

⦁ $n_D=n_B+w_{BD}=4+8=12$.Vì 12 > 11 (11 là nhãn hiện tại của D) nên ta giữ nguyên nhãn của D là 11.

⦁ $n_F=n_B+w_{BF}=4+6=10$.Vì $10<\mathrm{\infty }$ nên ta đổi nhãn của F thành 10.

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

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

⦁ $n_E=n_C+w_{CE}=5+6=11$.Vì $11<13$ (13 là nhãn hiện tại của E) nên ta đổi nhãn của E thành 11.

⦁ $n_F=n_C+w_{CF}=5+8=13$.Vì $13>10$  (10 là nhãn hiện tại của F) nên ta giữ nguyên nhãn của F là 10.

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 M thứ tư).

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

$n_N=n_F+w_{FN}=10+12=22$.Vì $22<\mathrm{\infty }$ nên ta đổi nhãn của N thành 22.

rong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là D, E nên ta tùy ý khoanh tròn đỉnh E (đỉnh gần M thứ năm).

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

$n_N=n_E+w_{EN}=11+7=18$.Vì $18<22$  (22 là nhãn hiện tại của N) nên ta đổi nhãn của N thành 18.

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

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

$n_N=n_D+w_{DN}=11+9=20$.Vì $20>18$ (18 là nhãn hiện tại của N) nên ta giữ nguyên nhãn của N là 18.

Lúc này, ta thấy chỉ còn đỉnh N chưa được khoanh tròn nên ta khoanh tròn đỉnh N (đỉnh gần M thứ bảy).

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

$\begin{array}{l}{n}_N=18=n_E+w_{EN}=n_C+w_{CE}+w_{EN}=n_M+w_{MC}+w_{CE}+w_{EN}\\ =w_{MC}+w_{CE}+w_{EN}=l_{MCEN}.\end{array}$

Vậy MCEN là đường đi ngắn nhất từ đỉnh M đến N, với độ dài bằng 18.