174
правки
Изменения
→Алгоритм
== Алгоритм ==
Пусть <tex>d_i</tex> {{- --}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i = \gets \infty</tex>; <tex>d_s = \gets 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>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>
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.
== Псевдокод ==
