251
правка
Изменения
м
→Многоуровневые корзины (англ. multi-level buckets, MLB)
|}
Подходит только графов с целочисленными рёбрами.
* Будем складывать вершины в "корзины" <tex>B[i] = \{u \in B[i] : d(u)=i\}</tex>,* Наша наша структура данных будет поддерживать индекс <tex>L = \{\forall i : i<L \Rightarrow B[i] = \emptyset\}</tex>* На на каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>,* При при релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>d(u)</tex>.
Можно заметить, что при такой реализации, все операции с приоритетной очередью будут выполняться за <tex>O(1)</tex>. Тогда, для одноуровневой реализации время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> — максимальная длина ребра в графе.
