Tìm đường đi ngắn nhất từ đỉnh M đến N trong đồ thị có trọng số sau

Giải Chuyên đề Toán 11 Chân trời sáng tạo Bài tập cuối chuyên đề 2

Bài 10 trang 68 Chuyên đề Toán 11: Tìm đường đi ngắn nhất từ đỉnh M đến N trong đồ thị có trọng số sau:

Lời giải:

– 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 < ∞ nên ta đổi nhãn của A thành 3.

⦁ n_B = n_M + w_MB = 0 + 4 = 4.Vì 4 < ∞ nên ta đổi nhãn của B thành 4.

⦁ n_C = n_M + w_MC = 0 + 5 = 5.Vì 5 < ∞ 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 < ∞ nên ta đổi nhãn của D thành 11.

⦁ n_E = n_A + w_AE = 3 + 10 = 13.Vì 13 < ∞ 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 < ∞ 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 < ∞ nên ta đổi nhãn của N thành 22.

Trong 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:

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.

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