Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Поскольку необходимо пройти через пункт С, для решения задачи нужно найти самые короткие пути от A до C и от C до E.
Задачу нагляднее решать построив схему. Но можно решить и по таблице, путём рассуждений.
Прямой путь из A в C равен 4. Поищем путь короче. Можно пройти из A в B (длина пути 1), из B в C (2), получаем длину пути 1 + 2 = 3
Из пункта C можно пойти только в пункт D (так как в A и B уже были, а “каждый пункт можно посетить только один раз”). Длина пути из C в D равна 3. Из пункта D остаётся пойти только в пункт E (длина пути 2), так как остальные уже пройдены. Таким образом, путь из C в E равен 3 + 2 = 5.