262
правки
Изменения
м
→Калибровка(caliber)
При такой реализации, время работы алгоритма Дейкстры можно оценить как <tex>O(m+n(1+ \sqrt{C}))</tex>
===Калибровка(caliber)===Введём величину <b><i>калибр(caliber)</i></b> вершины <tex>c(v)</tex> - вес минимального ребра, входящего в <tex>v</tex> , или <tex>\infty</tex>, если в вершину не входит ни одно ребро. Будем говорить, что текущее значение <tex>d(v)</tex> точно, если оно равно длине пути <tex>s \rightsquigarrow v</tex>.
{{Лемма
|about = 1
Модифицируем нашу MLB - структуру: будем хранить помеченные вершины в двух группах: сет <tex>F</tex> и приоритетная очередь <tex>B</tex>, реализованная на MLB.
Алгоритм, приведённый ниже, называется <b><i>алгоритмом умной очереди(smart queue)</i></b>.
Вершины в <tex>F</tex> будут иметь точные метки. Если <tex>F</tex> непусто, мы удалим оттуда вершину и прорелаксируем всех её соседей. Если же <tex>F</tex> пусто, мы достанем из
