Разбор задания №4 ОГЭ по информатике: Поиск кратчайшего пути по таблице (графы)

Задание №4 в ОГЭ по информатике проверяет умение анализировать информацию, представленную в виде весовых таблиц (матриц смежности), и находить оптимальные маршруты между вершинами графа (населёнными пунктами).
За верное выполнение задания вы получаете 1 первичный балл. Это классическая задача на графы, которая легко и безошибочно решается при помощи аккуратного чертежа схемы дорог.

1. Теоретический фундамент: что нужно знать

Вся задача строится на математической модели, которая называется графом:

• Вершины графа — это населённые пункты (обозначаются буквами: A, B, C, D, E, F).
  
• Рёбра графа — это дороги, соединяющие пункты между собой.
  
• Взвешенный граф — граф, у каждого ребра которого есть числовое значение (длина дороги, время или стоимость проезда).
  

Как читать весовую таблицу?

В условии приведена квадратная таблица. Число на пересечении строки и столбца означает протяжённость дороги между соответствующими пунктами:

• Если в ячейке стоит число — между пунктами есть прямая дорога указанной длины.
  
• Если ячейка пустая — прямой дороги между пунктами нет.
  
• Таблица всегда симметрична относительно главной диагонали, потому что дороги двусторонние: протяжённость пути из A в B точно такая же, как из B в A.
  

2. Основные методы решения

Существует два надёжных способа решения:

1. Построение схемы графа (самый популярный и наглядный способ):
   
   • Рисуем вершины по кругу или в виде многоугольника.
     
   • Соединяем вершины линиями, подписывая длины дорог.
     
   • Наглядно перебираем все возможные маршруты и считаем их сумму.
     
2. Построение дерева путей (метод перебора от начальной точки):
   
   • Записываем начальную точку (например, A) и «ветками» пускаем все возможные пункты, куда из неё можно поехать.
     
   • Складываем длины и отсекаем ветки, которые заведомо длиннее уже найденного маршрута.
     

3. Универсальный пошаговый алгоритм решения

1. Расположите вершины на черновике: нарисуйте кружочки с буквами по кругу (так линии дорог будут меньше пересекаться).
   
2. Перенесите дороги из таблицы:
   
   • Просматривайте таблицу только выше главной диагонали (чтобы не рисовать каждую дорогу дважды).
     
   • Соединяйте пары точек отрезками и сразу подписывайте их длину.
     
3. Определите начальный и конечный пункт: отметьте их на рисунке (например, из A в E).
   
4. Проверьте особые условия (если они есть):
   
   • «проходящего через пункт C» — маршрут обязан зайти в C.
     
   • «не проходящего через пункт B» — вершину B и все идущие к ней дороги можно сразу вычеркнуть.
     
5. Выпишите все возможные маршруты без петель и посчитайте длину каждого.
   
6. Выберите наименьшее значение и запишите его в ответ.
   

4. Разбор типовых примеров из банка ФИПИ

Пример 1. Базовый поиск кратчайшего пути

Условие:Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, указанным в таблице.

Решение:

1. Выписываем все дороги из таблицы:
   
   • A — B = 2
     
   • A — C = 5
     
   • B — C = 1
     
   • B — D = 4
     
   • B — E = 7
     
   • C — D = 2
     
   • D — E = 3
     
2. Составляем и просчитываем возможные маршруты из A в E:
   
   • Прямого пути A — E нет.
     
   • Путь через B:
     
     • A → B → E = 2 + 7 = 9
       
     • A → B → D → E = 2 + 4 + 3 = 9
       
     • A → B → C → D → E = 2 + 1 + 2 + 3 = 8
       
   • Путь через C:
     
     • A → C → D → E = 5 + 2 + 3 = 10
       
     • A → C → B → E = 5 + 1 + 7 = 13
       
3. Сравниваем длины: 9, 9, 8, 10, 13.
   
4. Кратчайший маршрут — A → B → C → D → E, его длина равна 8.
   

Ответ: 8

Пример 2. Путь с обязательным промежуточным пунктом

Условие:Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице:
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C.

Решение:

Так как маршрут обязан проходить через пункт C, разобьём задачу на две независимые части:

1. Кратчайший путь из A в C
   
2. Кратчайший путь из C в F
   

Шаг 1: Ищем путь из A в C:

• Прямой путь: A → C = 6
  
• Через вершину B: A → B → C = 3 + 2 = 5
  
• Кратчайший путь из A в C равен 5 (маршрут A → B → C).
  

Шаг 2: Ищем путь из C в F:

• Через D: C → D → F = 1 + 6 = 7
  
• Через D и E: C → D → E → F = 1 + 2 + 3 = 6
  
• Через E напрямую: C → E → F = 4 + 3 = 7
  
• Кратчайший путь из C в F равен 6 (маршрут C → D → E → F).
  

Шаг 3: Складываем части пути:

• Длина полного пути: 5 + 6 = 11 (A → B → C → D → E → F).
  

Ответ: 11

Пример 3. Подвох с «прямой» дорогой

Условие:Между пунктами A, B, C, D построены дороги:
Найдите кратчайший путь между A и D.

Решение:

• Прямой путь: A → D = 12
  
• Путь через C: A → C → D = 9 + 3 = 12
  
• Путь в обход через B и C: A → B → C → D = 1 + 2 + 3 = 6
  

Вывод: Прямая дорога из таблицы (длиной 12) оказалась в два раза длиннее, чем обходной маршрут через все промежуточные вершины (длиной 6).
Ответ: 6

5. Распространённые ловушки и советы на экзамене

1. Ловушка прямой дороги:
   
   • Никогда не берите прямую дорогу из таблицы как окончательный ответ, не проверив обходные пути. Практически всегда путь «в объезд» через 2–3 промежуточных пункта оказывается короче.
     
2. Игнорирование обязательного пункта:
   
   • Если в условии сказано «проходящего через пункт N», сразу обведите букву N в кружок на черновике. Самый короткий маршрут без заезда в N будет считаться грубой ошибкой.
     
3. Ошибки сложения на черновике:
   
   • Перепроверяйте сумму чисел дважды. Часто при верном нахождении цепочки ученики ошибаются в устном счёте (например, 2 + 1 + 2 + 3 записывают как 7 вместо 8).
     
4. Повторный проезд через пункты (петли):
   
   • В кратчайшем пути пункты не должны повторяться. Маршрут вроде A → B → C → B → E не может быть оптимальным.

Памятка для ученика

┌─────────────────────────────────────────────────────────────┐
│              ЧЕК-ЛИСТ ДЛЯ ЗАДАНИЯ №4 ОГЭ                    │
├─────────────────────────────────────────────────────────────┤
│ 1. Нарисовать все вершины кругом на черновике.              │
│ 2. Соединить вершины дорогами строго по таблице.            │
│ 3. Подписать длину каждого ребра.                           │
│ 4. Проверить ограничения (обязательный пункт / запрет).     │
│ 5. Выписать 2–3 самых коротких маршрута и сложить длины.    │
│ 6. Проверить: нет ли более короткого обходного пути?        │
└─────────────────────────────────────────────────────────────┘