← На главную ОГЭ 🎮 К заданию 🔍 Поиск кратчайшего пути

📚 Теория: Задание 4 ОГЭ — Анализ простейшей модели объектов

🗺️ Что такое граф?

Граф — это математическая модель, состоящая из множества вершин (точек) и множества рёбер (линий, соединяющих вершины).

В заданиях ОГЭ графы используются для моделирования дорожных сетей, где:

Пример графа

A B C D E 2 3 4 5 1 6

📊 Матрица расстояний

Информация о графе может быть представлена в виде матрицы расстояний (таблицы), где:

Пример матрицы

A B C D E
A - 2 3 - -
B 2 - 4 5 -
C 3 4 - 1 -
D - 5 1 - 6
E - - - 6 -

Жёлтым выделены дороги из пункта A: до B (2 км) и до C (3 км).

🔍 Типы задач задания 4 ОГЭ

📍 Кратчайший путь между двумя пунктами

Найти минимальное расстояние от пункта X до пункта Y.

📍 Путь через определённый пункт

Найти кратчайший путь от X до Y, который обязательно проходит через пункт Z.

📝 Алгоритм решения

Основной способ решения задания 4 — построение дерева путей. Дерево наглядно показывает все возможные маршруты от начального пункта к конечному и помогает ничего не пропустить. Остальные способы (перебор списком и алгоритм Дейкстры) приведены ниже как дополнительные.

🛤️ Основной способ: построение дерева путей

От начального пункта последовательно «выращиваем» ветви ко всем пунктам, куда есть дорога из текущего, не возвращаясь в уже посещённые пункты:

  1. Начните с начального пункта — это корень дерева
  2. От корня проведите ветви ко всем пунктам, куда можно попасть напрямую
  3. На каждой ветви подпишите расстояние
  4. От каждого нового пункта проведите ветви дальше, не возвращаясь к уже посещённым
  5. Продолжайте, пока не достигнете конечного пункта
  6. Сложите расстояния вдоль каждой ветви от корня до конечного пункта
  7. Выберите путь с минимальной суммой

Пример дерева путей

Рассмотрим граф из примера выше и для поиска пути из A в E построим дерево всех возможных маршрутов:

A B C C D B D E E D E C D E E E E 0 2 3 6 7 7 4 5 ✓ 8 7 13 8 12 10 13 10 18 2 3 4 5 4 1 2 2 1 6 1 5 6 6 2 6 Кратчайший путь (5) Другие маршруты

Все возможные пути из A в E:

  • A → C → E = 3 + 2 = 5 км ← кратчайший!
  • A → B → C → E = 2 + 4 + 2 = 8 км
  • A → C → D → E = 3 + 1 + 6 = 10 км
  • A → B → D → C → E = 2 + 5 + 1 + 2 = 10 км
  • A → B → C → D → E = 2 + 4 + 1 + 6 = 13 км
  • A → B → D → E = 2 + 5 + 6 = 13 км
  • A → C → B → D → E = 3 + 4 + 5 + 6 = 18 км

Ответ: Кратчайший путь A → C → E = 5 км

Справа от каждой вершины указано накопленное расстояние от начального пункта A. Зелёным цветом выделен кратчайший путь.

⚠️ Важно!

Строя дерево, двигайтесь только по дорогам, указанным в таблице. Если ячейка пуста — дороги нет!

Дополнительно: перебор путей списком

Тот же результат можно получить, выписав все маршруты списком — без рисунка:

  1. Выпишите все возможные маршруты из начального пункта в конечный
  2. Для каждого маршрута посчитайте суммарное расстояние
  3. Выберите маршрут с минимальным расстоянием

Дополнительно: алгоритм Дейкстры (для больших графов)

Алгоритм пошагового нахождения кратчайшего пути:

  1. Отметьте начальную вершину расстоянием 0, остальные — ∞
  2. Выберите непосещённую вершину с минимальным расстоянием
  3. Для каждой соседней вершины пересчитайте расстояние через текущую
  4. Если новое расстояние меньше — обновите его
  5. Повторяйте шаги 2-4, пока не достигнете целевой вершины

✏️ Примеры решения задач

Пример 1: Кратчайший путь между двумя пунктами

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

A B C D E
A - 2 5 - -
B 2 - 3 - -
C 5 3 - 4 2
D - - 4 - 1
E - - 2 1 -
Решение (построение дерева путей):

Шаг 1: От корня A «выращиваем» ветви ко всем ещё не посещённым пунктам. Ветви, которые не приводят в D, не достраиваем (справа от каждой вершины — накопленная длина пути от A):
A B C D E D C D E D 0 2 5 9 7 8 ✓ 5 9 7 8 ✓ 2 3 4 2 1 5 4 2 1 Кратчайший маршрут (8) Другие маршруты
Шаг 2: Каждая ветвь, ведущая в D, — отдельный маршрут:
Путь 1: A → B → C → D
Расстояние: 2 + 3 + 4 = 9
Путь 2: A → B → C → E → D
Расстояние: 2 + 3 + 2 + 1 = 8 ← минимальный!
Путь 3: A → C → D
Расстояние: 5 + 4 = 9
Путь 4: A → C → E → D
Расстояние: 5 + 2 + 1 = 8 ← минимальный!
Ответ: 8

Пример 2: Путь через определённый пункт

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

A B C D E
A - 1 - - -
B 1 - 2 - 7
C - 2 - 3 4
D - - 3 - 2
E - 7 4 2 -
Решение (построение дерева путей):

Шаг 1: Построим дерево путей из A в E (справа от каждой вершины — накопленная длина пути от A):
A B C E D E E 0 1 3 7 ✓ 6 8 8 1 2 4 3 2 7 Кратчайший маршрут (7) Другие маршруты
Шаг 2: Выпишем маршруты из дерева и отметим те, что проходят через C:
Путь 1: A → B → C → E = 1 + 2 + 4 = 7 ✓ через C
Путь 2: A → B → C → D → E = 1 + 2 + 3 + 2 = 8 ✓ через C
Путь 3: A → B → E = 1 + 7 = 8 (без C — не подходит)
Ответ: 7

Пример 3: Граф с 6 вершинами

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

A B C D E F
A - 3 - - - -
B 3 - 1 - 4 -
C - 1 - 2 5 -
D - - 2 - 1 3
E - 4 5 1 - 2
F - - - 3 2 -
Решение (построение дерева путей):

Шаг 1: Построим дерево путей из A в F (справа от каждой вершины — накопленная длина пути от A):
A B C D F E F E F D F E F D F C D F 0 3 4 6 9 ✓ 7 9 ✓ 9 11 10 13 7 9 8 11 12 14 17 3 1 2 3 1 2 5 2 1 3 4 2 1 3 5 2 3 Кратчайший маршрут (9) Другие маршруты
Шаг 2: Выпишем маршруты из дерева. Подходящие — только ветви, проходящие через C:
Путь 1: A → B → C → D → F = 3 + 1 + 2 + 3 = 9 ✓ через C
Путь 2: A → B → C → D → E → F = 3 + 1 + 2 + 1 + 2 = 9 ✓ через C
Путь 3: A → B → C → E → F = 3 + 1 + 5 + 2 = 11 ✓ через C
Путь 4: A → B → C → E → D → F = 3 + 1 + 5 + 1 + 3 = 13 ✓ через C
Путь 5: A → B → E → C → D → F = 3 + 4 + 5 + 2 + 3 = 17 ✓ через C
Путь 6: A → B → E → F = 3 + 4 + 2 = 9 (без C — не подходит)
Путь 7: A → B → E → D → F = 3 + 4 + 1 + 3 = 11 (без C — не подходит)
Ответ: 9

⚠️ Частые ошибки

💡 Полезные советы

Как строить дерево путей

  • Корень дерева — начальный пункт
  • Из каждого пункта проводите ветви ко всем ещё не посещённым соседям
  • Подписывайте на ветвях протяжённость дорог
  • Заканчивайте ветвь, когда пришли в конечный пункт или в тупик
  • Сравнивайте длину всех ветвей, ведущих в конечный пункт

Быстрая проверка для задач «через пункт»

  1. Постройте дерево и оставьте только ветви, проходящие через нужный пункт (например, C)
  2. Среди них найдите ветвь с минимальной длиной

Короткая альтернатива: сложить кратчайший путь от начала до C и кратчайший путь от C до конца.

Проверка ответа

  • Убедитесь, что все дороги в пути существуют (есть в таблице)
  • Проверьте, что путь начинается и заканчивается в нужных пунктах
  • Если есть условие про промежуточный пункт — проверьте, что путь через него проходит

🎯 План решения задачи

  1. 📝 Внимательно прочитайте условие задачи
  2. 🔍 Определите начальный и конечный пункты, а также обязательные промежуточные пункты (если есть)
  3. 📊 Изучите таблицу расстояний
  4. 🌳 Постройте дерево путей от начального пункта к конечному
  5. 🔢 Посчитайте длину каждой ветви (маршрута) и сравните их
  6. ✅ Выберите кратчайший путь и запишите ответ