Cho đồ thị có trọng số như Hình 16.

a) Tính độ dài các đường đi ABCD, MBNCP.

b) Chỉ ra ba đường đi khác nhau từ M đến N và tính độ dài của chúng.

c) MBC có phải là đường đi ngắn nhất từ M đến C không?

a) Ta có:

⦁ l_ABCD = w_AB + w_BC + w_CD = 5 + 15 + 4 = 24.

⦁ l_MBNCP = w_MB + w_BN + w_NC + w_CP = 7 + 7 + 6 + 25 = 45.

Vậy độ dài các đường đi ABCD, MBNCP lần lượt là 24 và 45.

b) Ba đường đi khác nhau từ M đến N là: MAN, MBN, MABN.

Ta có:

⦁ l_MAN = w_MA + w_AN = 5 + 9 = 14.

⦁ l_MBN = w_MB + w_BN = 7 + 7 = 14.

⦁ l_MABN = w_MA + w_AB + w_BN = 5 + 5 + 7 = 17.

Vậy ba đường đi khác nhau từ M đến N là MAN, MBN, MABN có độ dài lần lượt bằng 14; 14; 17.

c) Ta có MANC là một đường đi từ M đến C.

Mà l_MANC = w_MA + w_AN + w_NC = 5 + 9 + 6 = 20 và l_MBC = w_MB + w_BC = 7 + 15 = 22.

Vì 20 < 22 nên l_MANC < l_MBC.

Vậy MBC không phải là đường đi ngắn nhất từ M đến C.