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

Алгоритм Левита (англ. Levit's 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] — вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две очереди:

[math]M_1^{'}[/math] — основная очередь
[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 : u [math]\in V[/math]
   d[v] [math]\leftarrow \infty[/math]
d[s] [math]\leftarrow 0[/math]
[math]M_1^{'}[/math].push(s)
for u : u [math]\neq[/math] s  and uv [math]\in V[/math]
   [math]M_2[/math].push(u)
while [math]M_1^{'} \neq \varnothing[/math] and [math]M_1^{''} \neq \varnothing[/math]
   if [math]M_1^{''} \neq \varnothing[/math]
      int u [math]=[/math] [math]M_1^{''}[/math].pop()
   else :
      int u [math]=[/math] [math]M_1{'}[/math].pop()
   for v : uv [math]\in E[/math]
      if v [math]\in M_2[/math]
         [math]M_1^{'}[/math].push(v)
         [math]M_2[/math].remove(v)
         d[v] [math]=[/math] min(d[v], d[u] [math]+[/math] [math]w_{uv}[/math])
      if v [math]\in M_1[/math]
         d[v] = min(d[v], d[u] [math]+[/math] [math]w_{uv}[/math])
      if v [math]\in M_0[/math] and d[v] [math]\gt [/math] d[u] [math]+[/math] [math]w_{uv}[/math]
         [math]M_1^{''}[/math].push(v)
         [math]M_0[/math].remove(v)
         d[v] [math]=[/math] d[u] [math]+[/math] [math]w_{uv}[/math]
   [math]M_0[/math].push(u)

Доказательство

Лемма:

Алгоритм отработает за конечное время

Доказательство:

Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из в тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в . Тогда за конечное число шагов все вершины окажутся в .

Лемма:

В конце работы алгоритма не найдется такое ребро , что его релаксация будет успешной

Доказательство:

Предположим обратное. Тогда рассмотрим 2 случая:

Вершина [math]u[/math] попала в [math]M_0[/math] позже [math]v[/math]. Тогда должна была произойти релаксация ребра [math]uv[/math] и она была неуспешной. Значит, такого варианта не может быть
Вершина [math]u[/math] попала в [math]M_0[/math] раньше [math]v[/math]. Заметим, что с момента последнего попадания [math]u[/math] в [math]M_0[/math] расстояние до нее не менялось (иначе, вершина была бы извлечена из [math]M_0[/math]). Вес ребра [math]uv[/math] тоже не меняется. Значит, и релаксация ребра [math]uv[/math] ничего не даст

Противоречие.

Из двух предыдущих лемм напрямую следует корректность алгоритма.

Сложность

В худшем случае алгоритм Левита работает за экспоненциальное время. Достаточно рассмотреть полный граф [math]K_n[/math] с достаточно большим n и такими весами, что: [math]w_{uv} = 0[/math], если [math]u \neq 1[/math] и [math]w_{uv} = n - v + 2[/math], если [math]u = 1[/math].Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм Форда Беллмана и не многим хуже алгоритма Дейкстры.

Источники

Алгоритм Левита - Википедия
Алгоритм Левита
И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.

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