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

Алгоритм Левита (англ. 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] становится пустым.

Псевдокод

Для хранения вершин используем следующие структуры данных:

• [math]M_0[/math] — хеш-таблица,
• [math]M_1[/math] — основная и срочная очереди,
• [math]M_2[/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].add([math]u[/math])
while [math]M_1^{'} \neq \varnothing[/math] and [math]M_1^{''} \neq \varnothing[/math]
   [math]u=(M_1^{''} = \varnothing[/math] [math]?[/math] [math]M_1^{'}[/math].pop() [math]:[/math] [math]M_1{''}[/math].pop()[math])[/math]
   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 [math]v[/math] [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].add([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]M_1{''}[/math] и [math]M_1{'}[/math] дек и добавляя вершины из [math]M_0[/math] в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время, так делать не рекомендуется.

В плохих случаях алгоритм Левита работает за [math]O(n^2m)[/math]. Рассмотрим полный граф [math]K_n[/math] с [math]n[/math] вершинами и такими [math]m[/math] рёбрами, идущими в лексикографическом порядке:

• для всех вершин [math]1 \lt i \lt j \leqslant n[/math] вес ребра [math](i,j) = j - i - 1[/math], т.е. количество вершин между [math]i[/math] и [math]j[/math]; [math]w_{i,i+1}=0[/math],
• ребро [math](1,n)[/math] веса [math]0[/math],
• для всех вершин [math]1 \lt i \lt n[/math] вес ребра [math](1,i) = w_{1,i+1} + i - 1[/math]; от [math]1[/math] до [math]i[/math] вершины расстояние равно [math]\sum\limits_{k=i-1}^{n-2}k[/math].

Ясно, что кратчайший путь до каждой вершины равен [math]0[/math], но в плохом случае алгоритм при подсчёте вершины [math]i[/math] будет пересчитывать все вершины до неё (кроме первой). На [math]1[/math] шаге в очередь положат вершины от [math]2[/math] до [math]n[/math], причём вершину [math]1[/math] из [math]M_0[/math] больше не достанут. На следующем шаге добавлений не произойдёт, так как вершины больше [math]2[/math] уже в очереди. На [math]3[/math] шаге алгоритм улучшит расстояние до вершины [math]2[/math] на [math]1[/math] (что видно из веса рёбер [math](1,2)[/math] и [math](1,3)[/math], равных [math]\sum\limits_{k=1}^{n-2}k[/math] и [math]\sum\limits_{k=2}^{n-2}k[/math] соответственно), так что её добавят в [math]M_1{''}[/math] и обработают на [math]4[/math] шаге (релаксаций не происходит). На следующем шаге из обычной очереди достанут вершину [math]4[/math], расстояние до неё, равное [math]\sum\limits_{k=3}^{n-2}k[/math], на [math]2[/math] меньше, чем расстояние до [math]2[/math] и [math]3[/math] вершин. Их добавят в срочную очередь, но так как [math]w_{24}-1=w_{34}[/math], то после подсчёта вершины [math]3[/math] вершину [math]2[/math] снова добавят в [math]M_1{''}[/math]. Затем дойдёт очередь до вершины [math]5[/math], что вызовет релаксацию предыдущих вершин [math]2,3,4[/math], затем прорелаксируют вершины [math]2,3[/math], и после вершина [math]2[/math]. Аналогично будут происходить релаксации всех вершин при обработке вершины [math]i[/math] из очереди [math]M_0[/math]. Таким образом, вершину [math]i[/math] будут добавлять в срочную очередь [math]n-i[/math] раз (добавление вершин из очереди [math]M_2[/math] с номером больше [math]i[/math]) [math]+[/math] количество добавлений "старшей" вершины [math]i+1[/math]. Количество добавлений вершины [math]i[/math] составит [math]1 + \sum\limits_{k=1}^{n-i}k[/math], а сумма всех добавлений примерно составит [math]O(nm)[/math]. При обработке каждой вершины приходится обходить [math]n-1[/math] ребер, что даёт оценку [math]O(n^2m)[/math]. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм Форда Беллмана и не многим уступает алгоритму Дейкстры.

См. также

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

Источники информации

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