Пути не дублируются, они просто остаются путями, которые алгоритм еще не исследовал. A * поддерживает открытый набор , это набор узлов, который алгоритм уже знает, как достичь (и какой ценой), но он еще не пытался их расширить.
На каждой итерации алгоритм выбирает узел, который расширяется из открытого набора (тот, который имеет наименьшую функцию f - функция f представляет собой сумму стоимости, которую алгоритм уже знает, что требуется для того, чтобы добраться до узла (g), и алгоритм оценивает, сколько будет стоить добраться от узла до цели (h, эвристика).
http://en.wikipedia.org/wiki/A*_search_algorithm
посмотрите на псевдокод, поскольку вы видите, что используется открытый набор. Итак, суть - дело не в том, что алгоритм работает путем дублирования \ копирования \ перемещения путей или узлов от одной итерации к другой - он просто выполняет свою работу с одной и той же коллекцией узлов (конечно, узлы добавляются и удаляются из коллекции).
Надеюсь, это поможет ...