Условие задачи:
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице.
1) 9
2) 11
3) 13
4) 15
Решение:
1) Для удобства отобразим табличные данные в виде графа. Для этого на листе расставляем точки — населенные пункты. В соответствии с таблицей соединяем их и подписываем расстояния.
2) Переберем все возможные пути из A в F:
A-B-C-E-F = 3+3+2+7 = 15
A-B-C-D-F = 3+3+5+3 = 14
A-C-E-F = 5+2+7 = 14
A-C-D-F = 5+5+3 = 13
A-F = 15
Можно вести отсчет от F до А, т. е. из конечно пункта в начальный.
Из F можно попасть в А длина = 15 (1 вариант ответа)
Из F можно попасть в D длина = 3
Из D можно попасть в С длина = 5
Из С можно попасть в А длина = 5 (сумма = 13, 2 вариант ответа)
Из F можно попасть в Е длина = 7
Из Е можно попасть в В длина = 2
Как видно, кратчайший вариант A-C-D-F = 13 км.
ВНИМАНИЕ: Чтобы не запутаться, рекомендуется перебирать пункты в алфавитном порядке.
Ответ: 3
