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

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

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

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


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

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