2. Между населёнными пунктами A, B, C, D, E построены дороги. Их протяжённость (в километрах): A–B — 3, A–C — 3, B–C — 2, B–D — 1, B–E — 4, C–D — 5. Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по указанным дорогам; каждый пункт можно посетить только один раз.

Question

Вопрос:

Accepted Answer

Сравним основные пути из A в D: A–B–D имеет длину 3 + 1 = 4 км; A–C–D — 3 + 5 = 8 км; A–C–B–D — 3 + 2 + 1 = 6 км. Самый короткий путь — A–B–D.

Ответ: 4 км.