Изменения

* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено (возможно, не окончательно),

# <tex>M_1^{'}</tex> {{---}} основная очередь,# <tex>M_1^{''}</tex> {{---}} срочная очередь;* <tex>M_2</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>M_2</tex>.pushadd(<tex>u</tex>)

'''int''' <tex>u</tex> '''if''' <tex>=(M_1^{''} \neq = \varnothing</tex> <tex>u = ?</tex> <tex>M_1^{''}</tex>.pop() '''else''' <tex>u = :</tex> <tex>M_1{''}</tex>.pop()<tex>)</tex>

'''else if''' <tex>v </tex> <tex>\in M_1</tex>

<tex>M_0</tex>.pushadd(<tex>u</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>w_{uv} =рёбрами, идущими в [[Лексикографический порядок|лексикографическом порядке]]:* для всех вершин <tex>1 < i < j \begin{cases} v leqslant n</tex> вес ребра <tex>(i,j) = j - u i - 1</tex>, & u т.е. количество вершин между <tex>i</tex> и <tex>j</tex>; <tex> w_{i,i+1; u }= 0</tex>,* ребро <tex>(1 и v = ,n\\)</tex> веса <tex>0</tex>, w_{un}*2, & u = для всех вершин <tex>1 < i < n</tex> вес ребра <tex>(1, v i) = n - 1 \\ w_{uv1,i+1} + v i - u, & u = 1, v < n/tex>; от <tex>1</tex> до <tex>i</tex> вершины расстояние равно <tex>\sum\limits_{k=i-1\end}^{casesn-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>i2</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-1</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>M_1{''}i</tex> составит <tex dpi="130">1 + \sum\limits_{k=1}^{n-i} k</tex> раз, а сумма всех добавлений примерно составит <tex>O(nm)</tex>. При обработке каждой вершины приходится обходить <tex>n-1</tex> ребер, что даёт оценку <tex>O(n^2m)</tex>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим хуже алгоритма уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].

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

* [http://e-maxx.ru/algo/levit_algorithm e-maxx — MAXimal :: algo :: Алгоритм Левита]