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

Сравним допустимые маршруты из A в D, не посещая пункт повторно:

• A–C–D: 4 + 5 = 9 км;
• A–E–D: 6 + 3 = 9 км;
• A–B–C–D: 2 + 1 + 5 = 8 км;
• A–C–E–D: 4 + 1 + 3 = 8 км.

Маршруты с общей длиной меньше 8 км отсутствуют.

Ответ: 8 км.