Изменения

'''Алгоритм Левита''' (англ. ''Levit 's algorithm'') находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

'''for''' u : u <tex>\inV</tex> V ''':''' d[v] <tex>d_v \gets</tex> <tex>leftarrow \infty</tex> d[s] <tex>d_s \gets leftarrow 0</tex> <tex>M_1^{''}</tex>.addpush(s) '''for''' u : u <tex>\neq</tex> s '''and''' uv <tex>\inV</tex> V ''':''' <tex>M_2</tex>.addpush(u) '''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex> ''':''' '''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':int''' u <tex>\gets=</tex> <tex>M_1^{''}</tex>.pop()

'''int''' u <tex>\gets=</tex> <tex>M_1{'}</tex>.pop() '''for''' v : uv <tex>\inE</tex> E ''':''' '''if''' v <tex>\in M_2</tex> ''':'''

relaxd[v] <tex>=</tex> min(uvd[v], d[u] <tex>+</tex> <tex>w_{uv}</tex>) '''if''' v <tex>\in M_1</tex> ''':''' relaxd[v] = min(uvd[v], d[u] + <tex>w_{uv}</tex>) '''if''' v <tex>\in M_0</tex> '''and''' d[v] <tex>></tex>d_v d[u] <tex> d_u + </tex> <tex>w_{uv}</tex> ''':'''

relax(d[v] <tex>=</tex> d[u] <tex>+</tex> <tex>w_{uv, d) }</tex> <tex>M_0</tex>.addpush(u)

В худшем случае алгоритм Левита работает за экспоненциальное время. Достаточно рассмотреть полный граф <tex>K_n</tex> с достаточно большим n и такими весами, что: <tex>w_{uv} = 0</tex>, если <tex>u \neq 1</tex> и <tex>w_{uv} = n - v + 2</tex>, если <tex>u = 1</tex>. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм [[Алгоритм Форда-Беллмана|Форда Беллмана]] и не многим хуже алгоритма [[Алгоритм Дейкстры|Дейкстры]].

* [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 Алгоритм Левита - MAXimal::algo]* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 228229-234231. [[Категория: Алгоритмы и структуры данных]][[Категория: Кратчайшие пути в графах]]