262
правки
Изменения
→(avoid)
Такой способ подходит, только если граф имеет относительно правильную форму. На практике обычно используется оптимизированная версия этого алгоритма.
====Избирательный (avoid)====Этот алгоритм добавляет ориентиры по одному, глядя на вершины, которые плохо покрыты текущим набором ориентиров <tex>S</tex>. Построим из случайно выбранной вершины <tex>r</tex> дерево кратчайших путей <tex>T_{r}</tex>. <b>Весом</b> каждой вершины <tex>v</tex> в этом дереве назовём разность между истинной длиной пути <tex>d(v,r)</tex> и нижней оценкой этой длины <tex>\underline{d}(v,r)</tex>, полученной по текущему набору ориентиров. <b>Размером</b> вершины <tex>v</tex> назовём сумму её веса и размеров всех её потомков в <tex>T_{r}</tex>. Если поддерево <tex>T_{r}</tex> с корнем в <tex>v</tex> содержит ориентир, размер <tex>v</tex> равен 0. Начиная с максимальной по размеру вершины, пойдём вниз по дереву <tex>T_{r}</tex> и найдём лист с максимальным размером. Примем его за новый ориентир.
=Ссылки=
