Изменения

==Улучшения алгоритма Дейкстры==

===Многоуровневые корзины(multi-level buckets, MLB)===

{| border="1" cellspacing="0" cellpadding="5" align="right"

|-

|}

Подходит только графов с целочисленными рёбрами.

* Будем складывать вершины в "корзины" <tex>B[i] \subset V: {d(u)=i} </tex>

* На каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>

* При релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>dist(u)</tex>

Для одного уровня корзин время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> - максимальная длина ребра в графе.