27
правок
Изменения
Нет описания правки
Изначально все вершины, кроме <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_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> становится пустым.
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.
}}
{{Лемма
Противоречие.
}}
Из двух предыдущих лемм напрямую следует корректность алгоритма.
== Сложность ==
В худшем случае алгоритм Левита работает за экспоненциальное время. Достаточно рассмотреть полный граф , например в полном графе <tex>K_n</tex> с достаточно большим n и такими весами, что: <tex>w_{uv} = \begin{cases} 0, & u > 1 \\ n - v + 1, & u = 1 \\\end{cases}</tex> при обработке <tex>i</tex>, если -ой вершины из множества <tex>u \neq 1M_2</tex> и будет происходить релаксация <tex>w_{uv} = n i- v + 21</tex>, если рёбер и их добавление в срочную <tex>u = 1M_1{''}</tex>очередь.Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим хуже алгоритма [[Алгоритм Дейкстры|Дейкстры]].
== Источники ==
