Информатика · ОГЭ, ЕГЭ · 4 мин чтения

Как найти кратчайший путь в небольшом графе?

Редакция Алгоса · Обновлено

Короткий ответ

В графе точки обозначают объекты, линии между ними — разрешённые переходы. Если у линий указаны длины, кратчайшим будет маршрут с наименьшей суммой этих чисел. Меньшее количество линий не гарантирует меньшую длину. Для небольшого графа выпиши допустимые маршруты, посчитай каждую сумму и сравни. Если переходы направленные, обязательно соблюдай направление стрелок.

Переведи рисунок в список связей

Точку графа называют вершиной, соединяющую линию ребром, число на ребре — его весом. В дорожной задаче это может быть расстояние или время. Сначала выясни, разрешено ли двигаться в обе стороны. Здесь разберём неориентированный граф: каждая дорога проходима туда и обратно, все длины положительны.

Почему нельзя выбирать только самое короткое ребро?

Короткий первый переход может привести к дорогому продолжению. Выбирают минимум полной суммы от старта до цели, а не минимум отдельного шага. Нужно учитывать, куда ведёт каждая дорога и сколько стоит оставшаяся часть пути.

Сравни все допустимые продолжения

Нужно пройти из A в D. Дороги: AB = 2, AC = 5, BC = 1, BD = 6, CD = 2. Прямой дороги AD нет. Для такого маленького графа можно перечислить маршруты без повторения вершин. Они видны в списке связей, даже если линии на рисунке пересекаются.

Схема и полные суммы
A --2-- B
|      /|
5     1 6
|    /  |
C --2-- D
A → B → D: 2 + 6 = 8.
A → C → D: 5 + 2 = 7.
A → B → C → D: 2 + 1 + 2 = 5.
A → C → B → D: 5 + 1 + 6 = 12.
Минимальная длина равна 5.

Пересечение линий не добавляет вершину

Если линии на чертеже пересеклись без отмеченной точки, новый переход не появляется. При положительных весах обход с возвращением в уже посещённую вершину только увеличит длину, поэтому здесь достаточно маршрутов без повторов. Для большого графа используют специальные алгоритмы; этот перебор предназначен для маленькой проверяемой схемы.

  1. Проверь каждую соседнюю пару вершин по списку дорог.
  2. Подпиши сумму рядом с полным маршрутом.
  3. Сравни все варианты, соблюдая ограничения условия.

Что запомнить

Кратчайший путь минимизирует полную сумму весов. Проверяй допустимость каждого перехода и не суди по количеству дорог.

Попробовать на Алгосе

Информатика для ОГЭ

В теме «Кратчайший путь» тренируй чтение схемы и проверку сумм всех допустимых маршрутов.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы