Cho đồ thị có trọng số như Hình 4. Đường đi ngắn nhất từ A đến C là

A. AEC.

B. AEFC.

C. AC.

D. AFC.

Đáp án đúng là: B

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

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

⦁ n_E = n_A + w_AE = 0 + 2 = 2. Vì 2 < ∞ nên ta đổi nhãn của E thành 2.

⦁ n_F = n_A + w_AF = 0 + 4 = 4. Vì 4 < ∞ nên ta đổi nhãn của F thành 4.

⦁ n_B = n_A + w_AB = 0 + 2,5 = 2,5. Vì 2,5 < ∞ nên ta đổi nhãn của B thành 2,5.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là E nên ta khoanh tròn đỉnh E (đỉ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 E gồm D, C, F, ta có:

⦁ n_D = n_E + w_ED = 2 + 3 = 5. Vì 5 < ∞ nên ta đổi nhãn của D thành 5.

⦁ n_C = n_E + w_EC = 2 + 5 = 7. Vì 7 < ∞ nên ta đổi nhãn của C thành 7.

⦁ n_F = n_E + w_EF = 2 + 1 = 3. Vì 3 < 4 (4 là nhãn hiện tại của F) nên ta đổi nhãn của F 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 thứ hai).

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

n_F = n_B + w_BF = 2,5 + 1,5 = 4. Vì 4 > 3 (3 là nhãn hiện tại của F) nên ta giữ nguyên nhãn của F là 3.

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

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

n_C = n_F + w_FC = 3 + 2 = 5. Vì 5 < 7 (7 là nhãn hiện tại của C) 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à C, D (đều có nhãn là 5), nhưng do ta cần tìm đường đi ngắn nhất từ A đến C nên ta ưu tiên khoanh tròn đỉnh C (đỉnh gần A thứ tư).

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

n_C = 5 = n_F + w_FC

= n_E + w_EF + w_FC

= n_A + w_AE + w_EF + w_FC

= w_AE + w_EF + w_FC

= l_AEFC.

Vậy AEFC là đường đi ngắn nhất từ A đến C, với độ dài bằng 5.

Do đó ta chọn phương án B.