Задание 6: графы и кратчайший путь

Зачем нужны графы и кратчайший путь

В задании 6 легко потерять баллы не из-за сложной математики, а из-за спешки: перепутать направление стрелки, сложить не те расстояния или выбрать самый короткий участок вместо всего маршрута. Разберём понятный алгоритм, с которым ты сможешь уверенно читать схемы, находить путь между вершинами и проверять ответ. Графы встречаются не только на экзамене: они описывают дороги, маршруты сообщений, связи между объектами и переходы между состояниями.

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

Твоя цель обычно одна из двух: определить длину кратчайшего пути или найти сам маршрут. Не смешивай эти задачи с поиском самого короткого отдельного ребра: путь складывается из всех рёбер от начальной вершины до конечной.

Как читать граф по шагам

Сначала внимательно выпиши начальную и конечную вершины. Затем проверь, есть ли у рёбер направления. В ориентированном графе нельзя идти против стрелки, даже если визуально вершины соединены. После этого перенеси веса в отдельную запись или таблицу: так меньше риск считать расстояние «на глаз».

Полезно перечислить все разумные маршруты от старта к финишу. Для каждого сложи веса рёбер, а затем сравни полученные суммы. Если граф небольшой, такой способ надёжен и быстрее сложного алгоритма. Например, путь A → B → D имеет длину AB + BD, а путь A → C → D — длину AC + CD.

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

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

Алгоритм поиска кратчайшего пути

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

Если вариантов много, помогает таблица промежуточных расстояний. Сначала запиши расстояние до старта: 0. До соседних вершин поставь веса соответствующих рёбер. Затем сравнивай известное расстояние с новым вариантом: если через другую вершину получается меньше, замени значение. Для обычных задач ЕГЭ достаточно аккуратного перебора, но этот принцип похож на алгоритм Дейкстры.

Действие	Что проверить	Частая ошибка
1	Старт и финиш	Поменять их местами
2	Направление рёбер	Идти против стрелки
3	Полный маршрут	Сложить только один участок
4	Минимальную сумму	Выбрать визуально короткую линию

В ответе указывай именно то, что спрашивается: длину пути, последовательность вершин или номер маршрута.

Разобранный пример

Рассмотрим граф с начальной вершиной A и конечной D. Из A можно попасть в B по ребру 4 и в C по ребру 2. Из B в D ведёт ребро 7, а из C в D — ребро 5. Кроме того, между B и C есть переход B → C с весом 1. Найдём кратчайший путь из A в D.

Путь A → B → D: 4 + 7 = 11
Путь A → C → D: 2 + 5 = 7
Путь A → B → C → D: 4 + 1 + 5 = 10
Сравнение: 7 < 10 < 11
Ответ: кратчайший путь A → C → D, его длина равна 7

Обрати внимание: ребро B → C весит всего 1, но маршрут через него не становится лучшим. До B уже нужно пройти 4, а затем добавить 1 и 5. Поэтому сравнивать надо не отдельные рёбра, а суммы от старта до финиша.

Если в условии сказано, что некоторые дороги можно проходить в обе стороны, это должно быть явно обозначено. Не добавляй обратное направление самостоятельно: такая «додуманная» связь меняет множество маршрутов и ответ.

Типичные ошибки и проверка ответа

Первая ошибка — игнорировать стрелки. В неориентированном графе A — B означает движение в обе стороны, но в ориентированном A → B и B → A — разные возможности. Вторая ошибка — забыть один вес при сложении. После нахождения маршрута проговори его по вершинам и выпиши каждое ребро отдельным слагаемым.

Третья ошибка — выбрать путь с наименьшим первым шагом. Небольшое начало может вести к большому продолжению. Четвёртая — перепутать кратчайший путь с самым коротким маршрутом по количеству рёбер. Путь A → B → D может состоять из двух рёбер, но быть длиннее пути из трёх рёбер.

Пятая ошибка — не проверить существование маршрута. Иногда направление стрелок делает один из вариантов невозможным. Поставь рядом с каждым переходом отметку: разрешён он или нет. Если есть одинаковые минимальные значения, уточни, требуется ли назвать все кратчайшие пути или только их длину.

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

Граф — это вершины и соединяющие их рёбра. У стрелок есть направление, у рёбер могут быть веса. Кратчайший путь находят не по внешнему виду схемы и не по одному удачному шагу, а сравнением полных сумм от старта до финиша. Рабочий порядок такой: определить начало и конец, проверить стрелки, перечислить допустимые маршруты, сложить веса, сравнить результаты.

Перед отправкой ответа перечитай условие: возможно, спрашивается номер вершины, длина маршрута или последовательность переходов. Записывай вычисления аккуратно: ¾, 2⅓, √ и другие обозначения здесь обычно не нужны, но внимательность к каждому числу обязательна.

Следующий шаг — зарегистрируйся и реши 5 заданий бесплатно, чтобы закрепить алгоритм на разных схемах. Если готовишься к другим разделам экзамена, материалы по ЕГЭ помогут выстроить последовательную практику.