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

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

Псевдокод

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

[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])

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

Лемма:

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

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

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

Лемма:

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

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

Предположим обратное. Тогда рассмотрим 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]3n[/math] вершинами и такими рёбрами:

ребро [math](1,[/math] [math]2n + 1)[/math] веса [math]2^{n/2}[/math],
для нечётных вершин [math]i[/math] : идёт ребро [math](i,i+2)[/math] веса [math]2^{(3n-i)/2}[/math],
для вершин [math]i[/math]: [math]1 \leqslant i \lt 3n[/math] идёт ребро [math](i,i+1)[/math] веса [math]0[/math].

Ясно, что кратчайший путь до каждой вершины равен [math]0[/math], но в плохом случае алгоритм будет часто пересчитывать последние вершины. На 1 шаге в очередь положат две вершины: с номером [math]2[/math] (после нескольких шагов вершинам от [math]2[/math] до [math]2n + 1[/math] алгоритм сделает веса равными [math]0[/math]) и с номером [math]2n + 1[/math] (через такое же число шагов вершинам от [math]2n + 2[/math] до [math]3n[/math] будет задан вес [math]2^{n/2}[/math]). Оставшиеся [math]n-2[/math] вершины, находящиеся в очереди [math]M_0[/math], образуют последовательность маленьких циклов длины [math]3[/math], в которых два ребра нулевого веса. Каждый такой цикл увеличит количество добавлений следующих двух вершин в [math]M_1{''}[/math] на [math]1[/math]. Алгоритм будет часто пересчитывать расстояние до последних вершин, так как их часто добавляли в [math]M_1{''}[/math], что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм Форда Беллмана и не многим уступает алгоритму Дейкстры.

См. также

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

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

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