Базовый (1 балл)
Время: 3-5 мин
Построение графа
Дерево маршрутов
Задание №4 ОГЭ. Формальные описания реальных объектов (Графы)
Тема: Поиск кратчайшего пути между пунктами по весовой таблице расстояний
Дана весовая матрица расстояний между населенными пунктами A, B, C, D, E, F. Требуется найти длину кратчайшего пути между двумя заданными пунктами (часто с условием обязательного прохождения через промежуточный пункт C).
1. Алгоритм решения: дерево маршрутов
Самый безошибочный метод — нарисовать дерево возможных путей от начальной вершины:
- Корень дерева — стартовый пункт (например, A).
- Из таблицы смотрим всех соседей пункта A и рисуем ветки с весами: например,
A-B (2),A-C (4),A-D (7). - От каждого соседа продолжаем ветки дальше к финишу.
- Отсечение неперспективных веток: как только текущая сумма на ветке превысила уже найденный путь до финиша, ветку бросаем!
- Повторно в уже посещенные вершины на одной ветке заходить нельзя (путь должен быть простым).
Разновидности и прототипы задания на экзамене
1. Прямой кратчайший путь из A в F
Поиск минимального по сумме весов маршрута.
2. Кратчайший путь, проходящий через пункт C
Разбиение задачи на две части: (кратчайший из A в C) + (кратчайший из C в F).
Типичные ошибки
✕ Не так
Ошибка: Выбрать прямой путь A-F (длиной 15), не проверив обходные пути
Обходной путь A-B-C-F может быть 2 + 3 + 4 = 9 (значительно короче прямой дороги)!
✓ Так
Правильно: Всегда проверять многозвенные пути через транзитные пункты!
ГРОБ
ЛОВУШКА ОГЭ №4: Запрещенный пункт ('НЕ проходящий через пункт D')
В условии требуется найти путь из A в F, НЕ проходящий через промежуточный пункт D.
Как обойти
Сразу вычеркните всю строку и столбец пункта D из таблицы перед началом решения!
Лайфхаки на экзамене
- Таблица всегда симметрична относительно диагонали — достаточно смотреть только на числа ВЫШЕ главной диагонали.
- Если в условии сказано 'проходящий через пункт C', ищите кратчайший путь $A \to C$ и прибавьте кратчайший путь $C \to F$.