Изменения
→Многоуровневые корзины(multi-level buckets, MLB)
{| border="1" cellspacing="0" cellpadding="5" align="right"
|+ Сравнение различных структур данных для поиска кратчайшего пути на карте Европы(CPU 2,4GHz, 16MB RAM)
! Структура данных !! Время работы (сек)
|-
|-
| 8-куча || 11,52
|-
| MLB || 9,36
|-
| MLB + калибровка || 8,04
|-
|}
* При релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>dist(u)</tex>
При двухуровневой реализации будем поддерживать два уровня корзин: первый уровень будет соответствовать одноуровневой реализации, а корзины второго уровня будут содержать диапазон значений корзин первого уровня, которые в них входят.
Соответственно, нам нужно поддерживать два индекса <tex>L_{top}</tex> и <tex>L_{bottom}</tex> для каждого из уровней соответственно.
При такой реализации, время работы алгоритма Дейкстры можно оценить как <tex>O(m+n(1+\sqrt({C)}))</tex>
===Калибровка(caliber)===
Введём величину "калибр" вершины <tex>v</tex>- вес минимального ребра, входящего в <tex>v</tex>.
