Алгоритм Левита — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
# <tex>M_1^{''}</tex> {{---}} срочная очередь;
 
# <tex>M_1^{''}</tex> {{---}} срочная очередь;
 
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.
 
* <tex>M_2</tex> {{---}} вершины, расстояние до которых еще не вычислено.
 +
 +
Для хранения вершин используем следующие структуры данных:
 +
* <tex>M_0</tex> {{---}} хэш-сет,
 +
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],
 +
* <tex>M_2</tex> {{---}} хэш-сет.
  
 
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).
 
Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex> (в любую из очередей).
Строка 64: Строка 69:
 
== Сложность ==
 
== Сложность ==
  
В плохих случаях алгоритм Левита работает за экспоненциальное время. Рассмотрим граф с <tex>3\cdot n</tex> вершинами и такими рёбрами: от вершины <tex>1</tex> до <tex>n</tex> ребро веса <tex>2^n</tex>, цепь <tex>n-1</tex> рёбер через одну вершину (<tex>n</tex>, <tex>n+2</tex> <tex>...</tex> <tex>3 \cdot n</tex>; вес <tex>i</tex>-ого звена <tex>2^{n-i}</tex>), а также цепь рёбер от <tex>1</tex> до <tex>3 \cdot n</tex> (вес каждого звена <tex>0</tex>). Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм будет постепенно улучшать расстояние до последней вершины, пересчитывая его огромное число раз, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].
+
В плохих случаях алгоритм Левита работает за экспоненциальное время. Рассмотрим граф с <tex>3n</tex> вершинами и такими рёбрами:
 +
* ребро <tex>(1,</tex> <tex>2n + 1)</tex> веса <tex>2^{n/2}</tex>,
 +
* для нечётных вершин <tex>i</tex> : <tex>2 \cdot n+1 \leqslant i \leqslant 3n</tex> идёт ребро <tex>(i,i+2)</tex> веса <tex>2^{(3n-i)/2}</tex>,
 +
* для вершин <tex>i</tex>: <tex>1 \leqslant i < 3n</tex> идёт ребро <tex>(i,i+1)</tex> веса <tex>0</tex>.
 +
Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм будет часто пересчитывать последние вершины. На 1 шаге в очередь положат две вершины: с номером <tex>2</tex> (после нескольких шагов вершинам от <tex>2</tex> до <tex>2n + 1</tex> алгоритм сделает веса равными <tex>0</tex>) и с номером <tex>2n + 1</tex> (через такое же число шагов вершинам от <tex>2n + 2</tex> до <tex>3n</tex> будет задан вес <tex>2^{n/2}</tex>). Оставшиеся <tex>n-2</tex> вершины находятся в очереди <tex>M_0</tex>, алгоритм начнёт часто пересчитывать их вес, что приведёт к их многократному добавлению в <tex>M_1{''}</tex>, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].
  
 
==См. также==
 
==См. также==

Версия 17:10, 8 ноября 2015

Алгоритм Левита (англ. 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]M_0[/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])

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

Лемма:
Алгоритм отработает за конечное время
Доказательство:
[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 случая:

  1. Вершина [math]u[/math] попала в [math]M_0[/math] позже [math]v[/math]. Тогда должна была произойти релаксация ребра [math]uv[/math] и она была неуспешной. Значит, такого варианта не может быть
  2. Вершина [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]3n[/math] вершинами и такими рёбрами:

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

См. также

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