В этой статье рассмотрим решение задач на нахождение кратчайшего маршрута. Данная задача в ОГЭ оценивается в 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 ОГЭ по информатике 2017

Схема к задаче 3 ОГЭ по информатике

Ну а теперь по данной схеме найти кратчайший путь от А до Е будет легче. Давайте проанализируем данный граф. Попасть в пункт Е мы можем только из пункта С (так как в пункт Е есть только один путь и он из пункта С). Значит задача упрощается и нам нужно найти кратчайший путь до пункта С. А их всего 3:

  • AC = 5
  • ABC = 2+1 = 3
  • ADC = 1 + 3 = 4

И кратчайший из них — ABC. Получается, что кратчайший путь из A в E это путь по маршруту ABCE и его длина 2+1+2 = 5. Это и есть ответ — 2) 5.