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

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

Содержание

1 Алгоритм
2 Псевдокод
3 Доказательство
4 Сложность
5 См. также
6 Источники информации

Алгоритм

Пусть [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 [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]3\cdot n[/math] вершинами и такими рёбрами: от вершины [math]1[/math] до [math]n[/math] ребро веса [math]2^n[/math], цепь [math]n-1[/math] рёбер через одну вершину ([math]n[/math], [math]n+2[/math] [math]...[/math] [math]3 \cdot n[/math]; вес [math]i[/math]-ого звена [math]2^{n-i}[/math]), а также цепь рёбер от [math]1[/math] до [math]3 \cdot n[/math] (вес каждого звена [math]0[/math]). Ясно, что кратчайший путь до каждой вершины равен [math]0[/math], но в плохом случае алгоритм будет постепенно улучшать расстояние до последней вершины, пересчитывая его огромное число раз, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм Форда Беллмана и не многим уступает алгоритму Дейкстры.

См. также

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

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

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

Содержание