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