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

Алгоритм Левита (Levit algorithm) находит расстояние от заданной вершины [math]s[/math] до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

Алгоритм

Пусть [math]d_i[/math] — текущая длина кратчайшего пути до вершины [math]i[/math]. Изначально, все элементы [math]d[/math], кроме [math]s[/math]-го равны бесконечности; [math]d[s] = 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]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] становится пустым.

Псевдокод

for u [math]\in[/math] V :
   [math]d_v \gets[/math] [math]\infty[/math]
[math]d_s \gets 0[/math]

[math]M_1^{''}[/math].add(s)
for u [math]\neq[/math] s [math]\in[/math] V :
   [math]M_2[/math].add(u)

while [math]M_1 \neq \varnothing[/math] :
   if [math]M_1^{''} \neq \varnothing[/math] :
      u [math]\gets[/math] [math]M_1^{''}[/math].pop()
   else :
      u [math]\gets[/math] [math]M_1{'}[/math].pop()

   for uv [math]\in[/math] E :
      if v [math]\in M_2[/math] :
         [math]M_1^{'}[/math].push(v)
         relax(uv)
      if v [math]\in M_1[/math] :
         relax(uv)
      if v [math]\in M_0[/math] and [math]d_v \gt  d_u + w_{uv}[/math] :
         [math]M_1^{''}[/math].push(v)
         relax(uv)

   [math]M_0[/math].add(u)

Сложность

В худшем случае алгоритм Левита работает за [math]\bf O(|V| \cdot 2^{|V|})[/math]. Это происходит вследствие того, что некоторые вершины приходится обрабатывать повторно. Однако эксперементы показывают, что для реальных графов(например, карт дорог) данный алгоритм оказывается достаточно быстрым и эксперементальная оценка данного алгоритма составляет [math]\bf O(|E| \cdot log |V|)[/math].

См. также

• Алгоритм A*
• Алгоритм Дейкстры
• Алгоритм Джонсона
• Алгоритм Флойда
• Алгоритм Форда-Беллмана

Источники

• Алгоритм Левита - Википедия, свободная энциклопедия
• Алгоритм Левита - MAXimal::algo
• И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.