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