27
правок
Изменения
Нет описания правки
Разделим вершины на три множества:
* <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_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_1</tex> становится пустым.
== Сложность ==
В худшем случае плохих случаях алгоритм Левита работает за экспоненциальное времяочень долго. Например, в полном графе <tex>K_n</tex> с достаточно большим <tex>n </tex> и весами <tex>w_{uv} =
\begin{cases}
v - u - 1, & u > 1; \\ w_{un}\cdot2, & u = 1 и , v = n- 1 \\ w_{un}*n-2, & u = 1, v = n - 1 \\
w_{uv+1} + v - u, & u = 1, v < n-1
\end{cases}</tex>, рёбра идут в [[Лексикографический порядок|лексикографическом порядке]]. Добавление вершины <tex>i</tex>-ой вершины в очередь и последующая её обработка влекут добавление из <tex>M_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= \dfrac 12\cdot(n-i)\cdot(n-i+1)</tex> раз, всего в <tex>M_1{''}</tex> будет <tex>\dfrac 16\cdot n\cdot(n^2-3n+2)</tex> добавлений. В очень плохих случаях вершина <tex>i</tex> может помещаться в очередь <tex>M_1{''}</tex> до <tex>2^{n-i}</tex> раз, что даёт экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим хуже алгоритма уступает алгоритму [[Алгоритм Дейкстры|Дейкстры]].
==См. также==
