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

Материал из Викиконспекты
Перейти к: навигация, поиск

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