Cho đồ thị có trọng số như Hình 6. Tìm tất cả các đường đi từ A đến T

Giải Chuyên đề Toán 11 Chân trời sáng tạo Bài 3: Bài toán tìm đường đi ngắn nhất

Khám phá 2 trang 61 Chuyên đề Toán 11: Cho đồ thị có trọng số như Hình 6.

a) Tìm tất cả các đường đi từ A đến T (đi qua mỗi đỉnh nhiều nhất một lần) và tính độ dài của mỗi đường đi đó.

b) Từ đó, tìm đường đi ngắn nhất từ A đến T.

Lời giải:

a) Tất cả các đường đi từ A đến T (đi qua mỗi đỉnh nhiều nhất một lần) là: ABDT, ACDT, ACET, ACDET, ACEDT, ABDET, ABDCET.

Ta có:

⦁ l_ABDT = w_AB + w_BD + w_DT = 4 + 7 + 3 = 14;

⦁ l_ACDT = w_AC + w_CD + w_DT = 2 + 6 + 3 = 11;

⦁ l_ACET = w_AC + w_CE + w_ET = 2 + 12 + 5 = 19;

⦁ l_ACDET = w_AC + w_CD + w_DE + w_ET = 2 + 6 + 4 + 5 = 17;

⦁ l_ACEDT = w_AC + w_CE + w_ED + w_DT = 2 + 12 + 4 + 3 = 21;

⦁ l_ABDET = w_AB + w_BD + w_DE + w_ET = 4 + 7 + 4 + 5 = 20;

⦁ l_ABDCET = w_AB + w_BD + w_DC + w_CE + w_ET = 4 + 7 + 6 + 12 + 5 = 34.

b) Vì 11 < 14 < 17 < 19 < 20 < 21 < 34.

Nên l_ACDT < l_ABDT < l_ACDET < l_ACET < l_ABDET < l_ACEDT < l_ABDCET.

Vậy đường đi ngắn nhất từ A đến T là ACDT (có độ dài bằng 11).