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

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

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 [math]u : u \in V[/math]
   [math]d[u] = \infty[/math]
[math]d[s] = 0[/math]
[math]M_1^{'}[/math].push([math]s[/math])
for [math]u : u \neq s[/math] and [math]u \in V[/math]
   [math]M_2[/math].push([math]u[/math])
while [math]M_1^{'} \neq \varnothing[/math] and [math]M_1^{''} \neq \varnothing[/math]
   int [math]u[/math]
   if [math]M_1^{''} \neq \varnothing[/math]
      [math]u = M_1^{''}[/math].pop()
   else
      [math]u = M_1{'}[/math].pop()
   for [math]v : uv \in E[/math]
      if [math]v \in M_2[/math]
         [math]M_1^{'}[/math].push([math]v[/math])
         [math]M_2[/math].remove([math]v[/math])
         [math]d[v] =[/math] min([math]d[v], d[u] + w_{uv}[/math])
      else if v [math]\in M_1[/math]
         [math]d[v] =[/math] min([math]d[v], d[u] + w_{uv}[/math])
      else if [math]v \in M_0[/math] and [math]d[v] \gt  d[u] + w_{uv}[/math]
         [math]M_1^{''}[/math].push([math]v[/math])
         [math]M_0[/math].remove([math]v[/math])
         [math]d[v] = d[u] + w_{uv}[/math]
   [math]M_0[/math].push([math]u[/math])

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

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

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

[math]\triangleright[/math]

Предположим обратное. Тогда рассмотрим 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]\triangleleft[/math]

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

Сложность

В плохих случаях алгоритм Левита работает очень долго. Например, в полном графе [math]K_n[/math] с достаточно большим [math]n[/math] и весами [math]w_{uv} = \begin{cases} v - u - 1, & u \gt 1\\ w_{un}\cdot2, & u = 1, v = n - 1 \\ n-2, & u = 1, v = n\\ w_{uv+1} + v - u, & u = 1, v \lt n-1 \end{cases}[/math], рёбра идут в лексикографическом порядке. Добавление вершины [math]i[/math] в очередь и последующая её обработка влекут добавление из [math]M_0[/math] в [math]M_1{''}[/math] всех её предыдущих вершин, начиная со [math]2[/math]-ой; дойдя до вершины [math]i-1[/math], в [math]M_1{''}[/math] снова добавятся вершины меньше [math]i-1[/math] (кроме первой). Таким образом, вершину [math]i[/math] добавят в [math]M_1{''}[/math] [math]\sum\limits_{k=1}^{n-i}k = \dfrac 12\cdot(n-i)\cdot(n-i+1)[/math] раз, всего в [math]M_1{''}[/math] будет [math]\dfrac 16\cdot n\cdot(n^2-3n+2)[/math] добавлений. В очень плохих случаях вершина [math]i[/math] может помещаться в очередь [math]M_1{''}[/math] до [math]2^{n-i}[/math] раз, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм Форда Беллмана и не многим уступает алгоритму Дейкстры.

См. также

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

Источники

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