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