Изменения
→Алгоритм
== Алгоритм ==
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех все элементы <tex>d</tex>, кроме <tex>i \neq s : d_i \gets \infty</tex>-го равны бесконечности; <tex>d_s \gets d[s] = 0</tex>.
Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычисленновычислено
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>(в любую из очередей).
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество очередь <tex>M_1^{''}</tex> не пустопуста, то вершина берется из негонее, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>(производится релаксация ребра <tex>uv</tex>)
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
