Информатика · ОГЭ, ЕГЭ · 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.
Пересечение линий не добавляет вершину
Если линии на чертеже пересеклись без отмеченной точки, новый переход не появляется. При положительных весах обход с возвращением в уже посещённую вершину только увеличит длину, поэтому здесь достаточно маршрутов без повторов. Для большого графа используют специальные алгоритмы; этот перебор предназначен для маленькой проверяемой схемы.
- Проверь каждую соседнюю пару вершин по списку дорог.
- Подпиши сумму рядом с полным маршрутом.
- Сравни все варианты, соблюдая ограничения условия.
Что запомнить
Кратчайший путь минимизирует полную сумму весов. Проверяй допустимость каждого перехода и не суди по количеству дорог.
Попробовать на Алгосе
Информатика для ОГЭ
В теме «Кратчайший путь» тренируй чтение схемы и проверку сумм всех допустимых маршрутов.
Перейти к курсу Все курсы