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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 2 участников)
Строка 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> (в любую из очередей).
Строка 28: Строка 23:
  
 
== Псевдокод ==
 
== Псевдокод ==
 +
 +
Для хранения вершин используем следующие структуры данных:
 +
* <tex>M_0</tex> {{---}} [[Хеш-таблица|хеш-таблица]],
 +
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],
 +
* <tex>M_2</tex> {{---}} [[Хеш-таблица|хеш-таблица]].
  
 
  '''for''' <tex>u : u \in V</tex>
 
  '''for''' <tex>u : u \in V</tex>
Строка 69: Строка 69:
 
== Сложность ==
 
== Сложность ==
  
В плохих случаях алгоритм Левита работает за экспоненциальное время. Рассмотрим граф с <tex>3n</tex> вершинами и такими рёбрами:
+
При неправильной реализации алгоритма, используя вместо очередей <tex>M_1{''}</tex> и <tex>M_1{'}</tex> [[Персистентный дек|дек]] и добавляя вершины из <tex>M_0</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>O(n^2m)</tex>. Рассмотрим полный граф <tex>K_n</tex> с <tex>n</tex> вершинами и такими <tex>m</tex> рёбрами, идущими в [[Лексикографический порядок|лексикографическом порядке]]:
* для вершин <tex>i</tex>: <tex>1 \leqslant i < 3n</tex> идёт ребро <tex>(i,i+1)</tex> веса <tex>0</tex>.
+
* для всех вершин <tex>1 < i < j \leqslant n</tex> вес ребра <tex>(i,j) = j - i - 1</tex>, т.е. количество вершин между <tex>i</tex> и <tex>j</tex>; <tex>w_{i,i+1}=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>, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].
+
* ребро <tex>(1,n)</tex> веса <tex>0</tex>,
 +
* для всех вершин <tex>1 < i < n</tex> вес ребра <tex>(1,i) = w_{1,i+1} + i - 1</tex>; от <tex>1</tex> до <tex>i</tex> вершины расстояние равно <tex>\sum\limits_{k=i-1}^{n-2}k</tex>.
 +
Ясно, что кратчайший путь до каждой вершины равен <tex>0</tex>, но в плохом случае алгоритм при подсчёте вершины <tex>i</tex> будет пересчитывать все вершины до неё (кроме первой). На <tex>1</tex> шаге в очередь положат вершины от <tex>2</tex> до <tex>n</tex>, причём вершину <tex>1</tex> из <tex>M_0</tex> больше не достанут. На следующем шаге добавлений не произойдёт, так как вершины больше <tex>2</tex> уже в очереди. На <tex>3</tex> шаге алгоритм улучшит расстояние до вершины <tex>2</tex> на <tex>1</tex> (что видно из веса рёбер <tex>(1,2)</tex> и <tex>(1,3)</tex>, равных <tex>\sum\limits_{k=1}^{n-2}k</tex> и <tex>\sum\limits_{k=2}^{n-2}k</tex> соответственно), так что её добавят в <tex>M_1{''}</tex> и обработают на <tex>4</tex> шаге (релаксаций не происходит). На следующем шаге из обычной очереди достанут вершину <tex>4</tex>, расстояние до неё, равное <tex>\sum\limits_{k=3}^{n-2}k</tex>, на <tex>2</tex> меньше, чем расстояние до <tex>2</tex> и <tex>3</tex> вершин. Их добавят в срочную очередь, но так как <tex>w_{24}-1=w_{34}</tex>, то после подсчёта вершины <tex>3</tex> вершину <tex>2</tex> снова добавят в <tex>M_1{''}</tex>. Затем дойдёт очередь до вершины <tex>5</tex>, что вызовет релаксацию предыдущих вершин <tex>2,3,4</tex>, затем прорелаксируют вершины <tex>2,3</tex>, и после вершина <tex>2</tex>. Аналогично будут происходить релаксации всех вершин при обработке вершины <tex>i</tex> из очереди <tex>M_0</tex>. Таким образом, вершину <tex>i</tex> будут добавлять в срочную очередь <tex>n-i</tex> раз (добавление вершин из очереди <tex>M_2</tex> с номером больше <tex>i</tex>) <tex>+</tex> количество добавлений "старшей" вершины <tex>i+1</tex>. Количество добавлений вершины <tex>i</tex> составит <tex>1 + \sum\limits_{k=1}^{n-i}k</tex>, а сумма всех добавлений примерно составит <tex>O(nm)</tex>. При обработке каждой вершины приходится обходить <tex>n-1</tex> ребер, что даёт оценку <tex>O(n^2m)</tex>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].
  
 
==См. также==
 
==См. также==

Текущая версия на 19:35, 4 сентября 2022

Алгоритм Левита (англ. 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].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]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]. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм Форда Беллмана и не многим уступает алгоритму Дейкстры.

См. также

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