Изменения

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

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех все элементы <tex>d</tex>, кроме <tex>i \neq s : d_i \gets \infty</tex>-го равны бесконечности; <tex>d_s \gets d[s] = 0</tex>.

* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно),* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножествадве [[Очередь|очереди]]:# <tex>M_1^{'}</tex> {{---}} основная очередь,# <tex>M_1^{''}</tex> {{---}} срочная очередь;* <tex>M_2</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_2M_0</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_0M_2</tex> и <tex>d_v > d_u + w_{uv{---}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</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.