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

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

Алгоритм

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

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

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

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