Изменения
Нет описания правки
Мы будем рассматривать сеть автомобильных дорог:
* <tex>V</tex> - множество населённых пунктовперекрёстков
* <tex>E</tex> - множество дорог
* <tex>l(u,v)</tex> - среднее время, которое занимает проезд по дороге
==Алгоритм Дейкстры==
основная статья: [[Алгоритм Дейкстры]]
* на каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё
* завершает свою работу, когда цель достигнута (или просмотрены все вершины)
Скорость работы алгоритма Дейкстры сильно зависит от скорости операций с приоритетной очередью.
Для фибоначчиевых куч время работы алгоритма составляет <tex>O(V\log{V}+E)</tex>, для двоичных куч: <tex>O(E\log{V})</tex>
Поскольку мы рассматриваем сеть автомобильных дорог, то <tex>m = O(n)</tex>
