262
правки
Изменения
м
→ALT
* если некоторое ребро находится на кратчайшем пути между исходной точкой и ориентиром - по нему идём в первую очередь
[[Файл:ALT.jpg|right|thumbframe|рис. 1]]Будем использовать неравенство треугольника для нижних оценок пути(см. рис. 1). Пусть <tex>A</tex> - один из ориентиров, тогда:
*<tex>dist(v,w)\ge dist(A,w)-dist(A,v)</tex>
*<tex>dist(v,w)\ge dist(v,A)-dist(w,A)</tex>
Мы можем улучшить найденные ориентиры, если сначала, используя избирательный метод, найдём набор ориентиров в несколько (обычно, 4) раза больше, чем необходимо, а потом отсеем лишние минимизируя время запроса.
Оценим качество набора ориентиров <tex>S</tex> основываясь на покрытии дуг. Будем говорить, что ориентир <tex>L</tex> покрывает дугу <tex>(v,w)</tex>, если вершина <tex>v </tex> находится на кратчайшем пути <tex>L \rightsquigarrow w</tex>. То есть, <tex>\ell(v,w) = dist(L,w)-dist(L,v)</tex>, тогда такой выбор ориентира даст нам нижнюю границу для всех путей, содержащих <tex>(v,w)</tex>.
Если хотя бы один ориентир из <tex>S</tex> покрывает дугу <tex>(v,w)</tex>, то и весь <tex>S</tex> покрывает эту дугу.
