Граф, вершины и вес ребра простыми словами

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

Идея жадного выбора ближайшей вершины

Алгоритм держит для каждой вершины текущую оценку расстояния от старта: сначала у самого старта она равна нулю, у всех остальных — бесконечности. Дальше он повторяет один и тот же шаг. Из всех ещё не обработанных вершин выбирается та, у которой текущая оценка минимальна, — она объявляется обработанной, и расстояние до неё считается окончательным. Затем у всех соседей этой вершины проверяется, не короче ли путь через неё, чем известный им путь раньше; если короче — оценка соседа уменьшается. Шаг повторяется, пока не обработаны все нужные вершины.

  1. стартовой вершине присваивается расстояние 0, всем остальным — бесконечность
  2. из необработанных вершин берётся та, у которой сейчас минимальная оценка расстояния
  3. она помечается обработанной, и её расстояние считается окончательным и больше не меняется
  4. у каждого соседа этой вершины оценка обновляется, если путь через неё оказался короче
  5. цикл повторяется, пока не обработана нужная вершина или все вершины графа

Пошаговый пример на маленьком графе

Возьмём пять точек A, B, C, D, E и дороги между ними с весами в условных километрах: A-B — 4, A-C — 2, B-C — 1, B-D — 5, C-D — 8, C-E — 10, D-E — 2. Нужно найти кратчайший путь от A до E.

Интересная деталь этого примера — путь A-C-B-D-E длиннее по числу шагов, чем прямая связка A-B-D-E или A-C-E, но именно он даёт минимальную сумму весов. Жадный выбор ближайшей вершины на каждом шаге и приводит к глобально кратчайшему пути, хотя локально алгоритм ни разу не заглядывает в конец маршрута заранее.

Как восстановить сам путь, а не только его длину

Число 10 само по себе показывает только длину пути, а не его форму. Чтобы получить сам маршрут, при каждом улучшении оценки соседа алгоритм заодно запоминает, из какой вершины пришло это улучшение, — это называется предшественником. После завершения работы маршрут восстанавливается движением от конечной вершины назад по цепочке предшественников до самого старта. В примере выше цепочка предшественников для E выглядит так: E пришло от D, D — от B, B — от C, C — от A, и развёрнутый путь получается A-C-B-D-E.

Почему алгоритм ломается на отрицательных весах

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

Для графов с отрицательными весами существует другой алгоритм — Беллмана-Форда. Он работает медленнее Дейкстры, зато проверяет и пересматривает каждое ребро несколько раз подряд, поэтому не совершает той же ошибки преждевременного закрытия вершины.

Где этот алгоритм работает на практике

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

Чем Дейкстра отличается от соседних алгоритмов

Если все веса рёбер графа равны единице, алгоритм Дейкстры вырождается в обычный поиск в ширину — обход по слоям от старта наружу без всякого взвешивания. Алгоритм A star добавляет к той же жадной схеме эвристическую оценку оставшегося расстояния до цели, поэтому обычно находит путь быстрее, просматривая меньше лишних вершин, но требует разумной оценки этой эвристики для конкретной карты. Алгоритм Беллмана-Форда жертвует скоростью ради устойчивости к отрицательным весам, о которой шла речь выше.

Частые вопросы

Подходит ли алгоритм Дейкстры для навигатора с пробками?

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

Что делать, если в графе всё-таки есть отрицательные веса?

Использовать алгоритм Беллмана-Форда — он рассчитан именно на такие случаи и дополнительно умеет обнаруживать отрицательные циклы, при которых кратчайшего пути формально не существует вовсе.

Насколько быстро работает алгоритм на больших графах?

С очередью с приоритетом на основе кучи типичная оценка сложности — O((V+E) умножить на логарифм V), где V — число вершин, а E — число рёбер. На графах с миллионами вершин, вроде карты целой страны, поэтому применяют дополнительные ускорения вроде эвристик A star или предварительно построенных иерархий дорог.

Чем алгоритм Дейкстры отличается от простого поиска в ширину?

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