Тип 4. Между населенными пунктами A, B, C, D, E построены дороги, протяженность которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт C. Передвигаться можно только по дорогам, протяженность которых указана в таблице. Каждый пункт можно посетить только один раз.

По таблице доступны дороги: A–B — 2 км, A–C — 9 км, A–D — 4 км, B–C — 3 км, B–E — 5 км, C–D — 6 км, C–E — 10 км, D–E — 8 км.

Путь должен проходить через C, поэтому рассмотрим кратчайшие пути от A до C и от C до E без повторного посещения пунктов.

1. Кратчайший путь A–C — напрямую: 9 км. Путь A–B–C длиннее: 2 + 3 = 5 км. Следовательно, кратчайшее расстояние от A до C равно 5 км по маршруту A–B–C.
2. От C до E кратчайший путь — C–B–E: 3 + 5 = 8 км.

Объединить эти части нельзя: пункт B тогда был бы посещён дважды. Сравним допустимые маршруты через C: A–C–E — 9 + 10 = 19 км; A–D–C–E — 4 + 6 + 10 = 20 км; A–D–E–C — 4 + 8 + 10 = 22 км; A–B–C–E — 2 + 3 + 10 = 15 км; A–B–E–C — 2 + 5 + 10 = 17 км.

Ответ: 15 км, маршрут A–B–C–E.