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

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

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

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

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

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

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

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

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

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

Чтобы вычислить длину пути, нужно сложить длины всех рёбер, входящих в маршрут. Например, если путь проходит по рёбрам длиной 4, 1 и 3, его длина равна 4 + 1 + 3 = 8. Каждое ребро учитывают один раз, когда маршрут проходит по нему. Полученная сумма описывает весь путь, а не отдельный его участок.

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

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

Понятия для поиска кратчайшего пути

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

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

Разбор задач

Задача 1

Между пунктами A и B есть прямой путь длиной 4, а через C нужно пройти по рёбрам длиной 2 и 3. Требуется сравнить два маршрута от A до B: прямой и проходящий через C.

1. Для прямого маршрута записываем длину: 4.
2. Для маршрута через C складываем длины рёбер: 2 + 3 = 5.
3. Сравниваем 4 и 5: число 4 меньше.

Ответ: короче прямой маршрут A–B длиной 4.

Задача 2

Из A в D можно пройти через B или через C. Длины рёбер A–B и B–D равны 3 и 5, а A–C и C–D — 2 и 4. Нужно определить, какой из двух маршрутов имеет меньшую длину.

1. Первый маршрут записываем как A–B–D и считаем его длину: 3 + 5 = 8.
2. Второй маршрут записываем как A–C–D и считаем его длину: 2 + 4 = 6.
3. Сравниваем суммы: 6 меньше 8, значит, второй вариант выгоднее.

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

Задача 3

Даны рёбра: A–B = 2, A–C = 5, B–C = 1, B–D = 6, C–D = 2. Найдём кратчайший путь из A в D. В этой задаче особенно важно проверить маршрут с большим числом рёбер.

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.
4. Сравниваем 8, 7 и 5. Наименьшая сумма равна 5.

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

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

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

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

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

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

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

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

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

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

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