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