262
правки
Изменения
→Многоуровневые корзины (multi-level buckets, MLB)
* При релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>dist(u)</tex>
Можно заметить, что при такой реализации, все операции с приоритетной очередью будут выполняться за <tex>O(1)</tex>. Тогда, для одного уровня корзин одноуровневой реализации время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> - максимальная длина ребра в графе.
При двухуровневой реализации будем поддерживать два уровня корзин: первый уровень будет соответствовать одноуровневой реализации, а корзины второго уровня будут содержать диапазон значений корзин первого уровня, которые в них входят.
