262
правки
Изменения
м
→Многоуровневые корзины (multi-level buckets, MLB)
Можно заметить, что при такой реализации, все операции с приоритетной очередью будут выполняться за <tex>O(1)</tex>. Тогда, для одноуровневой реализации время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> - максимальная длина ребра в графе.
При двухуровневой реализации будем поддерживать два уровня корзин: первый уровень будет соответствовать одноуровневой реализации, а корзины второго уровня будут содержать диапазон значений корзин первого уровня, которые в них входят. СоответственноВ этом случае, нам нужно поддерживать два индекса <tex>L_{top}</tex> и <tex>L_{bottom}</tex> для каждого из уровней соответственно.
При такой реализации, время работы алгоритма Дейкстры можно оценить как <tex>O(m+n(1+ \sqrt{C}))</tex>
