Эвристики для поиска кратчайших путей

Данная статья - перевод выступления Renato F. Werneck в Microsoft Data Structures and Algorithms School в 2010 году.

Проблема поиска кратчайшего пути

Дано:

• ориентированный граф [math]G=(V,E)[/math]
• [math]l(u,v) \geqslant 0[/math]
• [math]|V|=n, |E|=m[/math]
• отправная точка - вершина [math]s[/math], пункт назначения - вершина [math]t[/math]

Цель: найти кратчайший путь [math] s \rightsquigarrow t[/math]

Мы будем рассматривать сеть автомобильных дорог:

• [math]V[/math] - множество перекрёстков
• [math]E[/math] - множество дорог
• [math]l(u,v)[/math] - среднее время, которое занимает проезд по дороге

Алгоритм Дейкстры

основная статья: Алгоритм Дейкстры

• на каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё
• завершает свою работу, когда цель достигнута (или просмотрены все вершины)

Скорость работы алгоритма Дейкстры сильно зависит от скорости операций с приоритетной очередью.

Для фибоначчиевых куч время работы алгоритма составляет [math]O(V\log{V}+E)[/math], для двоичных куч: [math]O(E\log{V})[/math]

Поскольку мы рассматриваем сеть автомобильных дорог, то [math]m = O(n)[/math]