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

Найдём кратчайшие расстояния от A:

1. До B: 2 км.
2. До C выгоднее ехать через B: 2 + 1 = 3 км (напрямую — 4 км).
3. До E кратчайший путь проходит через C: 3 + 1 = 4 км.
4. До D выгоднее ехать через E: 4 + 3 = 7 км; путь через C составляет 3 + 5 = 8 км.

Кратчайший маршрут: A–B–C–E–D.

Ответ: 7 км.