Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным
в таблице. Каждый пункт можно посетить только один раз.
РЕШЕНИЕ
Нарисуем граф, в котором отразим все пункты и длину дорог между ними.
Необходимо попасть из пункта А в пункт F
При этом обязательно проходя через пункт С
И этот путь должен быть кратчайшим.
Задачу можно разделить на две составляющие:
1) Нахождение кратчайшего пути из А в С
2) Нахождение кратчайшего пути из С в F
Нахождение кратчайшего пути из А в С:
Можем пойти по путям
ABC : 3+2=5
ABEC : 3+7+3=13
ABEDC : 3+7+1+1=12
ABDC : 3+3+1=7
Самый кратчайший путь из А в С - путь ABC, равный 5 км.
Нахождение кратчайшего пути из С в F:
CBEF : 2+7+2=11
CBDEF : 2+3+3+2=10
CEF : 3+2=5
CDEF : 1+1+2=4
Самый кратчайший путь из С в F - путь CDEF, равный 4 км.
Теперь просто складываем два кратчайших пути: ABC + CDEF = 5+4 = 9км
ОТВЕТ 9