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