Алгоритм Дейкстры


Дан ориентированный или неориентированный взвешенный граф с n вершинами и m рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина s. Требуется найти длины кратчайших путей из вершины s во все остальные вершины, а также предоставить способ вывода самих кратчайших путей.
 
Эта задача называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).

Выполняет такие же задачи как и 1-K BFS, но без учета K. Также как и 1-K BFS не умеет правильно обрабатывать отрицательные ребра

Алгоритм:
Сам алгоритм Дейкстры состоит из N итераций. На очередной итерации выбирается вершина V  с наименьшим расстоянием до нее из еще не отмеченных вершин, данная вершина становится отмеченной и из нее происходят релаксации соседних вершин.


 итоговая асимптотика алгоритма составляет: O(n2+ m)

Задача для тренировки:

Дейкстра: Начало (C++)


Задача для тренировки:

Дейкстра


Так как асимптотика наивной реализации алгоритма Дейкстра: \(O(n^2 + m)\), то с увеличением количества вершин скорость работы становиться неудовлетворительной.
 Для улучшения можно использовать различные структуры данных: Фибоначчиевы кучи, множества set или очередь с приоритетом priority_queue. 
Рассмотрим пример с set, в результате итоговая асимптотика получается: \(O(n log (m))\), подробнее.

Задача для тренировки:

Алгоритм Дейкстры за O(M logN) c set: Начало (C++)


Python

Для реализации на языке программирования Python. используйте кучу с приоритетом (priority queue).

Про реализацию Алгоритма Дейкстры с использованием модуля heapq на язке Python можно почитать здесь.

Задача для тренировки:

Алгоритм Дейкстры за O(M logN)

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