Изменения

'''for''' <tex>j \in V</tex> <font color="green">// найдем вершину с минимальным расстоянием</font>

Основной цикл выполняется <tex>V</tex> раз. Релаксация выполнится всего <tex>E</tex> раз. В реализации алгоритма присутствует функция выбора вершины с минимальным значением <tex>d</tex>, асимптотика её и релаксация по всем рёбрам для данной вершины. Асимптотика работы зависит от реализации.

{| borderclass="1wikitable" cellpadding="5" cellspacing="0" style="text-align:center"! Структура данных ! Время работы

! rowspan="2" |Наивная реализация! colspan="3" |<tex>O(V^Время работы! rowspan="2+E)</tex>" | Описание

| align="center" | Наивная реализация| align="center" | <tex>O(n)</tex>| align="center" | <tex>O(1)</tex>| align="center" | <tex>O(n^2 + m)</tex>| align="center" | <tex>n</tex> раз осуществляем поиск вершины с минимальной величиной <tex>d</tex> среди <tex>O(n)</tex> непомеченных вершин и <tex>m</tex> раз проводим релаксацию за <tex>O(1)</tex>. Для плотных графов (<tex>m \approx n^2</tex>) данная асимптотика является оптимальной.|-| align="center" | [[Двоичная куча]]| align="center" | <tex>O(\log{n})</tex>| align="center" | <tex>O(\log{n})</tex>| align="center" | <tex>O(m\log{n})</tex>| align="center" | Используя двоичную кучу можно выполнять операции извлечения минимума и обновления элемента за <tex>O(\log{n})</tex>. Тогда время работы алгоритма Дейкстры составит <tex>O(n\log{n} + m\log{n}) = O(m\log{n})</tex>. |-| align="center" |[[Фибоначчиевы кучи|Фибоначчиева куча]]|align="center" | <tex>O(\log{n})</tex>| align="center" | <tex>O(1)</tex>| align="center" | <tex>O(n\log{n} + m)</tex>| align="center" | Используя Фибоначчиевы кучи можно выполнять операции извлечения минимума за <tex>O(\log{n})</tex> и обновления элемента за <tex>O(1)</tex>. Таким образом, время работы алгоритма составит <tex>O(Vn\log{Vn}+Em)</tex>.