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