Изменения
→Оценка сложности
== Оценка сложности ==
Основной цикл выполняется <tex>V</tex> раз. Релаксация выполниться всего <tex>E</tex> раз. В реализации алгоритма присутствует функция ''argmin''выбора вершины с минимальным значением <tex>d</tex>, асимптотика её работы зависит от реализации.
Таким образом:
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных для хранения множества <tex>V \setminus S</tex>!style="background:#f2f2f2"|Асимптотика времени Время работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|КучаДвоичная куча
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}
== Источники ==
