174
правки
Изменения
→Алгоритм
== Алгоритм ==
Пусть <tex>d_i</tex> - текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i = \infty</tex>; <tex>d_s = 0</tex>.
Разделим вершины на три '''множества''':
* <tex>M_0</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_0</tex>. Для каждого ребра <tex>uv</tex>:
* если <tex>v \in M_2</tex>, то переносим <tex>v</tex> в <tex>M_1</tex> и релаксируем ребро <tex>uv</tex>
* если <tex>v \in M_1</tex>, то релаксируем ребро <tex>uv</tex>
* если <tex>c \in M_0</tex>, то переносим <tex>v</tex> в <tex>M_1</tex> и релаксируем ребро <tex>uv</tex>
Алгоритм завершается, когда множество <tex>M_1</tex> становится пустым.
== Псевдокод ==
