Изменения

* <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_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>w_{uv} =m</tex> рёбрами, идущими в [[Лексикографический порядок|лексикографическом порядке]]:* для всех вершин <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> 1\\ w_{uni,i+1}\cdot2=0</tex>, & u = * ребро <tex>(1, v = n - )</tex> веса <tex>0</tex>,* для всех вершин <tex>1 \\ < i < n-2, & u = </tex> вес ребра <tex>(1, v i) = n\\ 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>M_02</tex> в до <tex>M_1{''}n</tex> всех её предыдущих вершин, начиная со причём вершину <tex>21</tex> из <tex>M_0</tex>-ой; дойдя до больше не достанут. На следующем шаге добавлений не произойдёт, так как вершины больше <tex>i-12</tex>, уже в очереди. На <tex>M_1{''}3</tex> снова добавятся шаге алгоритм улучшит расстояние до вершины меньше <tex>i-2</tex> на <tex>1</tex> (кроме первой). Таким образом, вершину что видно из веса рёбер <tex>i(1,2)</tex> добавят в и <tex>M_1{''}(1,3)</tex> , равных <tex dpi="130">\sum\limits_{k=1}^{n-i2}k = </tex> и <tex>\dfrac 12sum\cdot(limits_{k=2}^{n-i)\cdot(n-i+1)2}k</tex> разсоответственно), всего так что её добавят в <tex>M_1{''}</tex> будет и обработают на <tex>4</tex> шаге (релаксаций не происходит). На следующем шаге из обычной очереди достанут вершину <tex>4</tex>, расстояние до неё, равное <tex>\dfrac 16sum\cdot limits_{k=3}^{n\cdot(n^-2}k</tex>, на <tex>2-3n+</tex> меньше, чем расстояние до <tex>2)</tex> добавленийи <tex>3</tex> вершин. В очень плохих случаях вершина Их добавят в срочную очередь, но так как <tex>w_{24}-1=w_{34}</tex>, то после подсчёта вершины <tex>3</tex> вершину <tex>i2</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>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].

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

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