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