Поиск кратчайшего пути в графе
💻 Информатика · 9 класс
Задача о кратчайшем пути
Одна из самых распространённых задач на графах — поиск кратчайшего пути между двумя вершинами. Граф здесь моделирует карту: вершины — это пункты (города, станции, перекрёстки), а рёбра с числами — дороги, у которых указана длина, время в пути или стоимость проезда. Требуется найти такой маршрут от начального пункта к конечному, у которого сумма чисел вдоль пути будет наименьшей.
Подобные задачи постоянно встречаются в жизни — их решают навигаторы, программы построения маршрутов и логистические системы. В школьном курсе разбирают основную идею на небольших графах.
Как рассуждать
В школьных задачах граф обычно небольшой, поэтому кратчайший путь находят перебором всех маршрутов. Выписывают каждый возможный путь от начальной вершины до конечной, складывают веса рёбер вдоль пути и выбирают тот маршрут, у которого сумма оказалась минимальной. Чтобы ничего не упустить, маршруты перебирают по порядку — например, сначала прямые, потом с одной промежуточной вершиной, потом с двумя.
Разбор примера
Дана таблица длин дорог между пунктами А, Б, В и Г. Прочерк означает отсутствие прямой дороги. Найдём кратчайший путь из А в Г.
| А | Б | В | Г | |
|---|---|---|---|---|
| А | — | 4 | 7 | — |
| Б | 4 | — | 1 | 5 |
| В | 7 | 1 | — | 2 |
| Г | — | 5 | 2 | — |
Выпишем все возможные маршруты из А в Г и подсчитаем их длины, складывая числа из таблицы:
А-Б-Г = 4 + 5 = 9
А-В-Г = 7 + 2 = 9
А-Б-В-Г = 4 + 1 + 2 = 7 (кратчайший)
А-В-Б-Г = 7 + 1 + 5 = 13
Наименьшая сумма — это 7, и она получается у маршрута А-Б-В-Г. Заметьте интересную деталь: путь с большим числом участков оказался короче прямых вариантов с двумя рёбрами. Это типичная «ловушка» подобных задач, на которую важно обращать внимание.
Чтобы перебор был аккуратным и ни один маршрут не потерялся, удобно строить дерево вариантов. Из начальной вершины проводят ветви ко всем соседям, из каждого соседа — к его соседям, и так далее, пока не доберёмся до конечной вершины. При этом нельзя возвращаться в уже посещённые на текущем пути вершины, иначе маршрут зациклится. Каждый путь от корня дерева до конечной вершины и есть один из возможных маршрутов, длину которого мы подсчитываем.
Частая ошибка. Останавливаться на первом найденном пути или рассматривать только прямые рёбра между нужными вершинами. Чтобы гарантированно найти кратчайший маршрут, нужно перебрать все возможные пути, включая обходные с несколькими промежуточными вершинами, и только потом сравнить их длины.
Кратко о главном
- Кратчайший путь — это маршрут с наименьшей суммой весов рёбер.
- В небольших графах его находят полным перебором всех маршрутов.
- Длину пути считают, складывая числа из таблицы расстояний.
- Обходной путь иногда оказывается короче прямого — проверяют все варианты.