Что делает: находит кратчайшие расстояния от одной вершины до всех остальных в взвешенном ориентированном графе БЕЗ рёбер отрицательного веса!

Чего С очередью с приоритетом С массивом
Время O([E + V]*logV) O(V^2 + E)
Память O(V) похуй

Как получается такая асимптотика по времени:

Время, затраченное на... с очередью с приоритетом с массивом
Инициализацию O(V) O(V)
Создание структуры O(V) O(V)
Extract-minimum из структуры V * O(logV) V * O(V)
Релаксацию рёбер E * O(logV) E * O(1)
** **** лучше для... ...задачи, где
Свойства графа E < V^2 E = O(V^2)

Общая идея:

Разделить граф на два подмножества: S - множество вершин, для которых вычислены окончательные веса кратчайших путей от s T - все остальные вершины, T = V \ S (множество вершин без множества S)

  1. По очереди выбирать u из T, у которой на данной итерации u.distance минимальная
  2. Добавить все рёбра, исходящие из u и прорелаксировать их

Реализация:

int main() {
	for u из G(V) do { // инициализация
		u.distance = INF
		u.parent = NULL
	}
	s.distance = 0 // инициализируем стартовую вершину

	vector<int> S = ø // множество вершин с окончательным
										// кратчайшем путём
	queue<int> Queue // заполняем очередь/массив вершинами
	while (!Queue.empty()) {
		u = Extract-min(Queue) // быстрее на очереди с приоритетом
		S.push_back(u)
		for v смежные с u
			Relax(edge(u,v)) // с соответствующими вызовами 
											// Decrease-key;
											// релаксация быстрее на массиве
	}
}

‼ Особенности алгоритма Дейкстра:

  1. не работает даже с рёбрами отрицательного веса!
  2. быстрее Беллмана-Форда, но опять же, больше ограничений на граф
  3. очередь с приоритетом лучше всего реализовывать на куче (bruh)
  4. жадный алгоритм

Визуализация: этим я займусь чуть попозже