Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт С. Передвигаться можно только по дорогам, указанным
в таблице. Каждый пункт можно посетить только один раз.
РЕШЕНИЕ
Изобразим на схеме все пункты, отметим длину дорог между ними. Выделим пункты A и D ,между которыми нужно найти кратчайший путь.
Отметим пункт С, в который обязательно необходимо зайти.
Разделим задачу на две части:
1. Найти кратчайшее расстояние между А и С
2. Найти кратчайшее расстояние между С и D.
1) Найдем кратчайший путь между А и С. Отметим все пути по которым можно пройти, найдем их длину.
AC 6км
AEC 3+2=5км - кратчайший путь
2) Найдем кратчайший путь между D и С. Отметим все пути по которым можно пройти, найдем их длину.
CD 2 км
AEC + CD = 5 + 2 =7км - кратчайший путь (условие , что в каждый пункт заходим один раз выполнено)
ОТВЕТ 7
