Графы и алгоритмы: узлы, связи и поиск лучшего маршрута

Где мы на карте

Логика дала правила перехода между утверждениями. В графе такие переходы становятся рёбрами между объектами, а алгоритм задаёт воспроизводимый порядок действий.

Сначала знакомый образ

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

Точное значение

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

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

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

Опорный сигнал урока

модель узлов и рёбер → единица веса → начальные расстояния → ближайшая вершина → обновить соседей → повторить → восстановить путь

Проговорите сигнал вслух. Для каждой стрелки объясните условие перехода и приведите пример, где это условие нарушается.

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

Для изображённого графа из A сначала получаем C=2, B=4. Через C улучшаем B до 3. Затем через B получаем D=8, через D — E=10, через E — F=13. Предшественники дают путь A→C→B→D→E→F, а сумма 2+1+5+2+3=13. Все другие незавершённые оценки не меньше 13.

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

Пример с уменьшающейся подсказкой

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

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

Воспроизведите без подсказки

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

Запишите также контрпример или граничный случай. Он показывает, понимаете ли вы условие, а не только запомнили ли последовательность действий.

Найдите и исправьте ошибку

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

Исправление полно, когда названа причина ошибки, восстановлен правильный шаг и показана независимая проверка.

Перенос в новую ситуацию

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

Отделите факты от предположений. Если данные собраны неслучайно или модель упрощает реальность, прямо укажите, какой вывод остаётся допустимым.

Задание

Обязательное. Для данного графа найдите кратчайшие расстояния от A до всех вершин таблицей Дейкстры. Затем удалите ребро D–E, повторите расчёт до F и объясните изменение. Отдельно приведите пример задачи, где нужен невзвешенный поиск в ширину, а не Дейкстра.

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

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

Открытая перспектива

Последний содержательный урок соединит данные, вероятность, функции, матрицы и графы в один проверяемый цикл моделирования.

Оглавление курса