Задание 1. Определение длины пути (поиск кратчайшего пути) — теория и разбор

В этом типе задания №1 вам даётся схема дорог (граф), но в отличие от первого типа, таблица содержит не просто отметки о наличии дороги (0/1 или звёздочки), а числа — длины дорог (веса рёбер). Задача обычно заключается в том, чтобы найти протяжённость кратчайшего пути между двумя пунктами или просто длину конкретного маршрута.

Что нужно знать

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

Вес ребра — числовая характеристика связи между вершинами.

Кратчайший путь — путь между двумя вершинами, сумма весов рёбер которого минимальна.

Для нахождения кратчайшего пути в небольших графах (обычно 5–6 вершин) достаточно полного перебора всех возможных маршрутов. Однако для надёжности можно использовать алгоритм Дейкстры — универсальный метод, который гарантированно находит кратчайший путь во взвешенном графе без отрицательных весов.

Почему перебор работает? Потому что в задании №1 граф всегда небольшой, число путей ограничено. Выписывая все маршруты от начальной до конечной вершины и суммируя веса, мы легко находим минимальное значение.

Типичная ошибка — забыть рассмотреть прямой путь, если он есть, или пропустить какой-либо маршрут. Всегда проверяйте все возможные варианты, особенно те, которые проходят через промежуточные вершины.

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

Ключевой приём: выписывайте все возможные пути от начальной до конечной вершины, суммируйте веса и выбирайте наименьшее значение.

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

Разбор примера

Иллюстрация 1 – схема графа с весами

Иллюстрация 2 – таблица длин дорог

В нашем примере граф имеет следующие рёбра и веса:

• A–B: 3
• A–C: 5
• A–D: 2
• B–C: 1
• B–E: 4
• C–D: 2
• C–E: 3
• D–F: 6
• E–F: 3

Соответствие между буквами и номерами в таблице (для удобства) — например, A=1, B=2, C=3, D=4, E=5, F=6. Тогда таблица длин дорог выглядит так:

(Прочерки означают отсутствие дороги.)

Как думать.

Нам нужно найти кратчайший путь из A (вершина 1) в F (вершина 6). Выпишем все возможные маршруты и их длины:

1. Прямой путь A–F: дороги нет (в таблице прочерк) → не подходит.
2. A–D–F: 2 + 6 = 8
3. A–C–E–F: 5 + 3 + 3 = 11
4. A–B–C–E–F: 3 + 1 + 3 + 3 = 10
5. A–B–E–F: 3 + 4 + 3 = 10
6. A–C–D–F: 5 + 2 + 6 = 13
7. A–B–C–D–F: 3 + 1 + 2 + 6 = 12
8. A–D–C–E–F: 2 + 2 + 3 + 3 = 10
9. A–B–C–E–D–F — не нужно, так как будет длиннее (уже больше 8).

Сравниваем все суммы: минимальная — 8 (путь A–D–F).

Ответ: 8 км

Данный пример взят из реального экзаменационного варианта (задание №1, вариант 54321). Все числа соответствуют оригинальному условию.