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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 42 промежуточные версии 6 участников)
Строка 1: Строка 1:
'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Данный алгоритм является модификацией [[Алгоритм Дейкстры|алгоритмы Дейкстры]], которая позволяет работать с ребрами отрицательного веса.
+
'''Алгоритм Левита''' (англ. ''Levit's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.
  
 
== Алгоритм ==
 
== Алгоритм ==
  
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.
+
Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, все элементы <tex>d</tex>, кроме <tex>s</tex>-го равны бесконечности; <tex>d[s] = 0</tex>.
  
 
Разделим вершины на три множества:
 
Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
+
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
+
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две [[Очередь|очереди]]:
# <tex>M_1^{'}</tex> {{---}} основная очередь
+
# <tex>M_1^{'}</tex> {{---}} основная очередь,
# <tex>M_1^{''}</tex> {{---}} срочная очередь
+
# <tex>M_1^{''}</tex> {{---}} срочная очередь;
* <tex>M_2</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> (в любую из очередей).
  
 +
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если очередь <tex>M_1^{''}</tex> не пуста, то вершина берется из нее, иначе из <tex>M_1^{'}</tex>. Для каждого ребра <tex>uv \in E</tex> возможны три случая:
 +
* <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex> (производится релаксация ребра <tex>uv</tex>),
 +
* <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>,
 +
* <tex>v \in M_0</tex>. Если при этом <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и вершина <tex>v</tex> помещается в <tex>M_1^{''}</tex>; иначе ничего не делаем.
 +
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.
  
'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
+
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
+
 
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
+
== Псевдокод ==
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
+
 
 +
Для хранения вершин используем следующие структуры данных:
 +
* <tex>M_0</tex> {{---}} [[Хеш-таблица|хеш-таблица]],
 +
* <tex>M_1</tex> {{---}} основная и срочная [[Очередь|очереди]],
 +
* <tex>M_2</tex> {{---}} [[Хеш-таблица|хеш-таблица]].
  
 +
'''for''' <tex>u : u \in V</tex>
 +
    <tex>d[u] = \infty</tex>
 +
<tex>d[s] = 0</tex>
 +
<tex>M_1^{'}</tex>.push(<tex>s</tex>)
 +
'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex>
 +
    <tex>M_2</tex>.add(<tex>u</tex>)
 +
'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex>
 +
    <tex>u=(M_1^{''} = \varnothing</tex> <tex>?</tex> <tex>M_1^{'}</tex>.pop() <tex>:</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex>
 +
    '''for''' <tex>v : uv \in E</tex>
 +
      '''if''' <tex>v \in M_2</tex>
 +
          <tex>M_1^{'}</tex>.push(<tex>v</tex>)
 +
          <tex>M_2</tex>.remove(<tex>v</tex>)
 +
          <tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)
 +
      '''else if''' <tex>v</tex> <tex>\in M_1</tex>
 +
          <tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)
 +
      '''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex>
 +
          <tex>M_1^{''}</tex>.push(<tex>v</tex>)
 +
          <tex>M_0</tex>.remove(<tex>v</tex>)
 +
          <tex>d[v] = d[u] + w_{uv}</tex>
 +
    <tex>M_0</tex>.add(<tex>u</tex>)
  
Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.
+
== Доказательство ==
 +
 
 +
{{Лемма
 +
|statement= Алгоритм отработает за конечное время
 +
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.
 +
}}
 +
 
 +
{{Лемма
 +
|statement= В конце работы алгоритма не найдется такое ребро <tex>uv</tex>, что его релаксация будет успешной
 +
|proof= Предположим обратное. Тогда рассмотрим 2 случая:
 +
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть
 +
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст
 +
Противоречие.
 +
}}
  
== Псевдокод ==
+
Из двух предыдущих лемм напрямую следует корректность алгоритма.
  
 
== Сложность ==
 
== Сложность ==
  
== См. также ==
+
При неправильной реализации алгоритма, используя вместо очередей <tex>M_1{''}</tex> и <tex>M_1{'}</tex> [[Персистентный дек|дек]] и добавляя вершины из <tex>M_0</tex> в начало дека, алгоритм в худшем случае будет работать за экспоненциальное время, так делать не рекомендуется.
 +
 
 +
В плохих случаях алгоритм Левита работает за <tex>O(n^2m)</tex>. Рассмотрим полный граф <tex>K_n</tex> с <tex>n</tex> вершинами и такими <tex>m</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>(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>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].
 +
 
 +
==См. также==
 +
* [[Алгоритм A*]]
 +
* [[Алгоритм Дейкстры]]
 +
* [[Алгоритм Джонсона]]
 +
* [[Алгоритм Флойда]]
 +
* [[Алгоритм Форда-Беллмана]]
 +
* [[Обход в ширину]]
 +
 
 +
== Источники информации==
 +
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Википедия — Алгоритм Левита]
 +
* [http://e-maxx.ru/algo/levit_algorithm MAXimal :: algo :: Алгоритм Левита]
 +
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.
  
== Источники ==
+
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Кратчайшие пути в графах]]

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

См. также

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