A*
m が Openリストにある場合、 f ′ ( m ) < f ( m ) {\displaystyle f'(m)<f(m)} であるなら、m を Open から削除し、 f ( m ) ← f ′ ( m ) {\displaystyle f(m)\leftarrow f'(m)} に置き換え、再び Open に挿入する(Open が正しくソートされていることを保証するため)。また、記録してある m の親を n に置き換える。 m が Closeリストにある場合、 f ′ ( m ) < f ( m ) {\displaystyle f'(m)<f(m)} であるなら f ( m ) ← f ′ ( m ) {\displaystyle f(m)\leftarrow f'(m)} として m を Openリストに移動する。また記録してある m の親を n に置き換える。
3 以降を繰り返す。
探索終了後、発見されたゴール n G {\displaystyle n_{G}} から親を順次たどっていくと S から ゴール n G {\displaystyle n_{G}} までの最短経路が得られる。
以上の流れを見れば、アルゴリズムが手続き的で、並列化が非常に難しいことがわかる。しかし、近年では HDA*、PBFS などの並列手法が開発され、特に HDA* は768コア以上の大規模並列計算環境にもスケールすることが実証されている。