Поиск кратчайшего пути

Определения и обозначения

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

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

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

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

Как это устроено

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

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

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

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

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

Элементы графа и их роль в задаче о кратчайшем пути

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

Разбор задач

Задача 1

Пункты A, B и C соединены дорогами AB длиной 4 км, BC длиной 3 км и AC длиной 9 км. Нужно найти кратчайший путь из A в C. Есть два варианта: дорога напрямую или маршрут через B.

1. Длина прямого пути A–C равна 9 км, потому что он состоит из одного ребра AC.
2. Для пути A–B–C складываем длины обоих участков: 4 + 3 = 7 км.
3. Сравниваем 7 км и 9 км: меньшая длина у маршрута через B.

Ответ: кратчайший путь — A–B–C, его длина 7 км. Считать нужно оба участка, хотя в маршруте через B дорог больше.

Задача 2

Даны рёбра AB = 2, AC = 5, BC = 1, BD = 6, CD = 2. Требуется найти кратчайший путь из A в D. Вершину D можно достичь из B или C, а к ним из A ведут разные варианты, поэтому сравним маршруты.

1. Через B можно пройти A–B–D: длина равна 2 + 6 = 8.
2. Через C можно пройти A–C–D: длина равна 5 + 2 = 7.
3. Также проверим путь A–B–C–D: 2 + 1 + 2 = 5. Путь A–C–B–D имеет длину 5 + 1 + 6 = 12.
4. Из найденных вариантов наименьшая сумма — 5. Других продолжений без повторного обхода этих связей к D нет: попасть в D можно только из B или C, а варианты подхода через каждую из них проверены.

Ответ: кратчайший путь A–B–C–D, его длина 5.

Задача 3

Дороги между пунктами имеют длины AB = 3, AC = 2, BC = 2, BD = 5, CD = 1, CE = 6, DE = 2. Нужно найти кратчайший маршрут из A в E и обосновать выбор. До E можно попасть из C или D, поэтому сравним пути, ведущие к этим пунктам.

1. Через C можно попасть в E напрямую: A–C–E имеет длину 2 + 6 = 8. Другой путь к C — A–B–C, его длина 3 + 2 = 5; затем дорога C–E даёт общую длину 11.
2. Через D можно проехать A–B–D–E: 3 + 5 + 2 = 10. Вариант A–C–D–E имеет длину 2 + 1 + 2 = 5.
3. Проверим и путь через B и C к D: A–B–C–D–E имеет длину 3 + 2 + 1 + 2 = 8. Также A–C–B–D–E даёт 2 + 2 + 5 + 2 = 11.
4. Сравниваем полученные варианты: 5, 8, 8, 10 и 11. Наименьшая длина равна 5; все способы попасть в E заканчиваются ребром CE или DE, и варианты подхода по этим рёбрам проверены.

Ответ: кратчайший маршрут A–C–D–E, его длина 5. Проверка путей к обоим соседям E показывает, что более короткого варианта нет.

Типичные ошибки

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

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

Третья ошибка — включать в маршрут переход, которого нет на схеме. Иногда кажется, что между близкими вершинами «должна быть» дорога, но в задаче учитываются только заданные рёбра. Перед вычислением проверь каждую пару соседних вершин маршрута на наличие соединения.

Четвёртая ошибка — сложить длины рёбер маршрута, который не ведёт от нужного начала к нужному концу. Это может произойти, если потерять одну из крайних вершин при записи пути. Сверь первую и последнюю вершины с условием, а затем убедись, что все промежуточные шаги соединены рёбрами.

Связь с другими темами

Для решения задач полезно уметь читать схемы и таблицы, находить последовательность связанных объектов и складывать натуральные числа. Эти навыки помогают правильно записать маршрут и вычислить его длину без пропусков. Поиск кратчайшего пути применяют в задачах о расстояниях, маршрутах и стоимости переходов. Работа с такими схемами подготавливает к дальнейшему изучению графов и алгоритмов поиска пути в информатике.

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

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