Алгоритм Левита

Алгоритм Левита находит расстояние от заданной вершины [math]s[/math] до всех остальных. Данный алгоритм является модификацией алгоритмы Дейкстры, которая позволяет работать с ребрами отрицательного веса.

Алгоритм

Пусть [math]d_i[/math] — текущая длина кратчайшего пути до вершины [math]i[/math]. Изначально, для всех [math]i \neq s : d_i \gets \infty[/math]; [math]d_s \gets 0[/math].

Разделим вершины на три множества:

• [math]M_0[/math] — вершины, расстояние до которых уже вычислено(возможно, не окончательно)
• [math]M_1[/math] — вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:

1. [math]M_1^{'}[/math] — основная очередь
2. [math]M_1^{''}[/math] — срочная очередь

• [math]M_2[/math] — вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме [math]s[/math] помещаются в множество [math]M_2[/math]. Вершина [math]s[/math] помещается в множество [math]M_1[/math].

Шаг алгоритма: выбирается вершина [math]u[/math] из [math]M_1[/math]. Если подмножество [math]M_1^{''}[/math] не пусто, то вершина берется из него, иначе из [math]M_1^{'}[/math]. Далее, для каждого ребра [math]uv \in E[/math]:

• если [math]v \in M_2[/math], то [math]v[/math] переводится в конец очереди [math]M_1^{'}[/math]. При этом [math]d_v \gets d_u + w_{uv}[/math]
• если [math]v \in M_1[/math], то происходит релаксация ребра [math]uv[/math]
• если [math]v \in M_0[/math] и [math]d_v \gt d_u + w_{uv}[/math], то происходит релаксация ребра [math]uv[/math] и [math]v[/math] помещается в [math]M_1^{''}[/math]

В конце шага помещаем вершину [math]u[/math] в множество [math]M_0[/math].

Алгоритм заканчивает работу, когда множество [math]M_1[/math] становится пустым.