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

Данная статья - перевод выступления 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] - среднее время, которое занимает проезд по дороге