Изменения

* <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>.

'''for''' <tex>u : u <tex>\in V</tex> <tex>d[vu] <tex>\leftarrow = \infty</tex> <tex>d[s] <tex>\leftarrow = 0</tex> <tex>M_1^{'}</tex>.push(<tex>s</tex>) '''for''' <tex>u : u <tex>\neqs</tex> s '''and''' uv <tex>u \in V</tex> <tex>M_2</tex>.push(<tex>u</tex>)

'''int''' u <tex>u =</tex> <tex>M_1^{''}</tex>.pop() '''else :''' '''int''' u <tex>u =</tex> <tex>M_1{'}</tex>.pop() '''for''' <tex>v : uv <tex>\in E</tex> '''if''' v <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>=</tex> min(<tex>d[v], d[u] <tex>+</tex> <tex>w_{uv}</tex>) '''else if''' v <tex>\in M_1</tex> <tex>d[v] = </tex> min(<tex>d[v], d[u] <tex>+</tex> <tex>w_{uv}</tex>) '''else if''' v <tex>v \in M_0</tex> '''and''' <tex>d[v] <tex>></tex> d[u] <tex>+</tex> <tex>w_{uv}</tex> <tex>M_1^{''}</tex>.push(<tex>v</tex>) <tex>M_0</tex>.remove(<tex>v</tex>) <tex>d[v] <tex>=</tex> d[u] <tex>+</tex> <tex>w_{uv}</tex> <tex>M_0</tex>.push(<tex>u</tex>)

В худшем случае алгоритм Левита работает за экспоненциальное время. Например, например в полном графе <tex>K_n</tex> с достаточно большим n и весами <tex>w_{uv} =

0v - u - 1, & u > 1 ; u = 1 и v = n\\ w_{un}*2, & u = 1, v = n - v 1 \\ w_{uv+ 1} + v - u, & u = 1 \\, v < n-1\end{cases}</tex> при обработке , рёбра идут в [[Лексикографический порядок|лексикографическом порядке]]. Добавление <tex>i</tex>-ой вершины в очередь и последующая её обработка влекут добавление из множества <tex>M_2M_0</tex> в <tex>M_1{''}</tex> будет происходить релаксация всех её предыдущих вершин, начиная со <tex>2</tex>-ой; дойдя до вершины <tex>i-1</tex> рёбер и их добавление , в <tex>M_1{''}</tex> снова добавятся вершины меньше <tex>i-1</tex>-ой (кроме первой). Таким образом, количество добавлений <tex>i</tex>-ой вершины в срочную <tex>M_1{''}</tex> очередьсоставит <tex dpi="130">\sum\limits_{k=1}^{n-i} k</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 e-maxx — Алгоритм Левита]