Изменения

<tex>M_1^{'}</tex>.push(<tex>s</tex>)

'''for''' <tex>u : u \neq s</tex> '''and''' <tex>u \in V</tex>

'''while''' <tex>M_1^{'} \neq \varnothing</tex> '''and''' <tex>M_1^{''} \neq \varnothing</tex>

'''for''' <tex>v : uv \in E</tex>

'''if''' <tex>v \in M_2</tex>

<tex>M_2</tex>.remove(<tex>v</tex>)

<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)

<tex>d[v] =</tex> min(<tex>d[v], d[u] + w_{uv}</tex>)

'''else if''' <tex>v \in M_0</tex> '''and''' <tex>d[v] > d[u] + w_{uv}</tex>

<tex>M_0</tex>.remove(<tex>v</tex>)

<tex>d[v] = d[u] + w_{uv}</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 Википедия — Алгоритм Левита]

* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., 4 издание, стр. 229-231.

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Кратчайшие пути в графах]]