Изменения
→Алгоритм Дейкстры
Скорость работы алгоритма Дейкстры сильно зависит от скорости операций с приоритетной очередью.
Поскольку мы рассматриваем сеть автомобильных дорог, то <tex>m = O(n)</tex> (граф планарен почти везде).
Для фибоначчиевых куч время работы алгоритма составляет <tex>O(V\log{V}+E)</tex>, для двоичных куч: <tex>O(E\log{V})</tex>
Но на практике чаще используются 2-, 4- и 8-ичные кучи: они более простые, оценка времени работы содержит меньшее количество скрытых констант.
==Улучшения алгоритма Дейкстры==
===Многоуровневые корзины(multi-level buckets, MLB)===
{| border="1" cellspacing="0" cellpadding="5" align="right"
|+ Сравнение различных структур данных для поиска кратчайшего пути на карте Европы
|}
Подходит только графов с целочисленными рёбрами.
* Будем складывать вершины в "корзины" <tex>B[i] \subset V: {d(u)=i} </tex>
* На каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>
* При релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>dist(u)</tex>
Для одного уровня корзин время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>СC</tex> - максимальная длина ребра в графе.
При двухуровневой реализации будем поддерживать два уровня корзин: первый уровень будет соответствовать одноуровневой реализации, а корзины второго уровня будут содержать диапазон значений корзин первого уровня, которые в них входят.
Соответственно, нам нужно поддерживать два индекса <tex>L_topL_{top}</tex> и <tex>L_bottomL_{bottom}</tex> для каждого из уровней соответственно.
При такой реализации, время работы алгоритма Дейкстры можно оценить как <tex>O(m+n(1+sqrt(C)))</tex>
