Алгоритм Дейкстры с очередью с приоритетами

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

Алгоритм Дейкстры: (1) инициализируйте dist[source] = 0, а для всех остальных вершин установите dist[all others] = inf. (2) Поместите (0, source) в минимальную кучу. (3) Извлеките вершину u с наименьшим расстоянием. Если она уже была посещена с меньшим расстоянием, пропустите её. (4) Для каждого соседа v вершины u: если dist[u] + weight(u,v) < dist[v], обновите dist[v] и поместите (dist[v], v) в кучу. (5) Повторяйте, пока куча не опустеет.

Модуль Python heapq реализует минимальную кучу. Представим граф в виде списка смежности: graph[u] = [(v, weight), ...]. В куче хранятся кортежи (distance, node). Мы используем множество посещённых вершин visited, чтобы пропускать устаревшие записи в куче — записи, добавленные до того, как был найден более короткий путь.

Рассмотрим граф с 5 вершинами и рёбрами: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Кратчайшие пути из вершины 0: до 1 через 0→2→1 со стоимостью 3, до 2 со стоимостью 1, до 3 через 0→2→1→3 со стоимостью 4, до 4 через 0→2→1→3→4 со стоимостью 7. Алгоритм Дейкстры находит все эти пути за один проход, а не только путь к одной целевой вершине.

Корректность алгоритма Дейкстры зависит от того, что после извлечения вершины из минимальной кучи её расстояние становится окончательным. Это верно только в том случае, если веса рёбер неотрицательны. При наличии отрицательного ребра u→v с весом -5 после посещения v мы можем обнаружить более короткий путь через u, но v уже помечена как посещённая. Одного отрицательного ребра достаточно, чтобы сделать все последующие вычисления расстояний неверными.

В этой задаче появляется ограничение: не более k пересадок. Стандартный алгоритм Дейкстры не учитывает количество переходов напрямую. Решение: расширить состояние до (cost, node, stops_remaining). Используйте алгоритм Дейкстры с этим кортежем или алгоритм Беллмана—Форда с k+1 проходами релаксации. Модифицированный алгоритм Дейкстры останавливается, когда stops_remaining достигает 0, предотвращая дальнейшие переходы.

С двоичной кучей алгоритм Дейкстры работает за O((V + E) log V): каждая вершина извлекается один раз (V извлечений), каждое ребро может привести к добавлению элемента (E добавлений), а каждая операция с кучей стоит O(log V). С кучей Фибоначчи оценка улучшается до O(E + V log V), но heapq в Python представляет собой двоичную кучу. Для разреженных графов (E ≈ V) вариант с двоичной кучей работает за O(V log V); для плотных графов (E ≈ V²) — за O(V² log V).

Чтобы восстановить сам путь, а не только расстояния, поддерживайте массив prev: при обновлении dist[v] устанавливайте prev[v] = u. После завершения алгоритма восстановите путь от источника до назначения, двигаясь назад: начните с dst, следуйте по указателям prev до source, а затем разверните полученный результат.

Если вершины представлены строками или непоследовательными целыми числами, используйте defaultdict(list) для списка смежности и обычный dict для расстояний. Это часто встречается в задачах LeetCode, например «Задержка в сети», где вершины пронумерованы от 1 до n. Не забудьте использовать dist = {node: inf for node in all_nodes} и проверить наличие недостижимых вершин после завершения алгоритма.

Для невзвешенных графов BFS находит кратчайшие пути за O(V + E), то есть быстрее, чем алгоритм Дейкстры за O((V+E) log V). Алгоритм Дейкстры обобщает BFS для взвешенных графов, используя очередь с приоритетом вместо обычной очереди FIFO. Если веса всех рёбер одинаковы, алгоритм Дейкстры сводится к BFS. Выбирайте BFS для невзвешенных графов, алгоритм Дейкстры — для неотрицательных весов, а Беллмана—Форда — для отрицательных весов.

В учебном варианте алгоритма Дейкстры используется очередь с приоритетом и операцией уменьшения ключа: когда расстояние до вершины улучшается, её приоритет обновляется на месте. Для этого нужна куча Фибоначчи, обеспечивающая сложность O(E + V log V), но реализовать её трудно. При используемом на собеседованиях подходе с ленивым удалением вместо этого добавляется новая запись, а устаревшие извлечённые элементы пропускаются — это проще и требует лишь постоянного множителя дополнительных затрат. В Python ленивое удаление с помощью heapq является стандартной реализацией алгоритма для собеседований.

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

В этом уроке вы узнали: алгоритм Дейкстры использует минимальную кучу для жадной обработки вершин в порядке возрастания текущего наилучшего расстояния, он работает за O((V+E) log V) и не справляется с рёбрами отрицательного веса, а устаревшие записи в куче обрабатываются проверкой множества посещённых вершин при извлечении. Далее мы рассмотрим алгоритм Беллмана—Форда, который обрабатывает отрицательные веса с помощью n-1 проходов релаксации.