* <tex>l(u,v)</tex> - среднее время, которое занимает проезд по дороге
==Алгоритм Дейкстры==
основная статья: [[Алгоритм Дейкстры]]
* на каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё
Скорость работы алгоритма Дейкстры сильно зависит от скорости операций с приоритетной очередью.
{| border="1" cellspacing="0" cellpadding="5" align="right"
|+ Сравнение различных структур данных для поиска кратчайшего пути на карте Европы
! Структура данных !! Время работы (сек)
|-
| Двоичная куча || 12,38
|-
| 4-куча || 11,53
|-
| 8-куча || 11,52
|-
|}
Поскольку мы рассматриваем сеть автомобильных дорог, то <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)===Подходит только графов с целочисленными рёбрами.* Будем складывать вершины в "корзины" <tex>B[i] \subset V: {d(u)=i} </tex>* Наша структура данных будет поддерживать индекс <tex>L: \forall B[i]: i<L \Rightarrow B[i] = \emptyset </tex>* На каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>* При релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>dist(u)</tex>Для одного уровня корзин время работы алгоритма Дейкстры можно оценить как <tex>m = O(nm+nC)</tex>, где <tex>С</tex> - максимальная длина ребра в графе. При двухуровневой реализации будем поддерживать два уровня корзин: первый уровень будет соответствовать одноуровневой реализации, а корзины второго уровня будут содержать диапазон значений корзин первого уровня, которые в них входят. Соответственно, нам нужно поддерживать два индекса <tex>L_top</tex> и <tex>L_bottom</tex> для каждого из уровней соответственно.
