Реконструкция пути
Результат типичного поиска проиллюстрирован на рисунке 14. Круг обозначает адресат пути. Серые ячейки, те которые никогда не будут посещены в процессе поиска по алгоритму. Темно-серым обозначено препятствие.
Стрелки указывают на те грани которые характеризуют 'на данный момент лучший из всех известных' путей по всем исследованным ячейкам, то есть значения ed[v] для вершин указаны острием стрелок. Для удаленных ячеек (не маркированы) данный путь будет оптимален до этих ячеек. Более толстые темные стрелки указывают наиболее дешевый путь к адресату.
Рисунок 14 - маленькая часть дерева A* поиска
Если нас интересовало только нахождение стоимости минимального пути, тогда мы могли бы пропустить сохранение значений ed[v] ( и таким образом сохранили бы по байту с каждого узла). Теперь можно легко использовать указатели возврата ed[v] от вершины адресата для нахождения оптимального пути. Мы начинаем с ячейки адресата и затем идем в противоположном направлении по отношению к направлению грани, сохраненной в текущей ячейке, это продолжается до тех пор пока мы не достигаем исходной ячейки. С помощью данного перебора просто обратить последовательность ячеек, посещенных в течение трассировки указателей возврата, для того чтобы произвести уже 'нормальный' путь от источника до адресата.
7.2.4