Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
РЕШЕНИЕ
Нарисуем граф, где наглядно отобразим все пункты и длину дорог между ними
Выделим те пункты, между которыми нужно найти кратчайший путь
Теперь сверху вниз проходим по всем возможным дорогам , которые ведут их пункта А в пункт D
ABCD
ACD
ACED
AED
AECD
Теперь посчитаем протяжённость всех дорог:
ABCD: 2+1+4=7
ACD: 4+4=8
ACED: 4+3+3=10
AED: 5+3=8
AECD: 5+3+4=12
Необходимо найти длину кратчайшего пути, значит ищем наименьшее из получившийся чисел. Это 7.
ОТВЕТ 7
