概要
A*(A-star)探索アルゴリズムは，重み付きグラフを入力することで，始点から終点への最短経路を出力するアルゴリズムである．
アルゴリズム
$f(v_i)=g(v_i)+h(v_i)$とする．ここで，$f(v)$は頂点$v$から終点への推定距離で，$g(v)$は始点から頂点$v$までの最小距離，$h(v)$は頂点$v$から終点への推定距離とする．$\mathrm{cost}(e_{ij})$を$e_{ij}$のコスト（重み）とする．
入力
頂点の集合$V$
辺の集合$E$（重みの情報も含む）
始点$v_s\in V$
終点$v_g\in V$（終点は複数であってもよい）
任意の頂点$v_i\in V$に対する$h(v_i)$
出力
$v_s$から$v_g$への最短距離とその経路
STEP1 初期化
OPENリストとCLOSEリストを用意し，OPENリストには始点$v_s$を入れる．また，CLOSEリストは空とする．また，
\begin{equation}
g(v_s)=0, f(v_s)=h(v_s)
\end{equation}
とする．
STEP2 反復による最短経路の探索
OPENリストに格納されている頂点から，$f(v_i)$が最小である頂点$v_i$を取り出す．（最初は$v_s$）
（このときOPENリストが空であればSTEP3に進む．）
$v_i$が$v_g$であれば反復を終了しSTEP3に進む．
$v_i$と隣接する（$v_i$から辺が直接伸びている先の）頂点をOPENリストに入れる．また，これらの頂点に対してそれぞれの$f'(v)$を以下のように計算する．
$v_i$と隣接する頂点$v_j$について，
\begin{eqnarray}
g(v_j)&=&g(v_i)+\mathrm{cost}(e_{ij})\\
f'(v_j)&=&g(v_j)+h(v_j)
\end{eqnarray}
- $v_j$がOPENリストに入っているとき，$f(v_j)>f'(v_j)$であれば$f(v_j):=f'(v_j)$とし，$v_j$の親（直前の頂点）を$v_i$とする．
- $v_j$がCLOSEリストに入っているとき，$f(v_j)>f'(v_j)$であれば$f(v_j):=f'(v_j)$とし，$v_j$をOPENリストに移動して$v_j$の親を$v_i$とする．
- $v_j$がどのリストにも入っていないとき，$f(v_j):=f'(v_j)$とし，$v_j$をOPENリストに入れて$v_j$の親を$v_i$とする．
（$:=$はここでは「右辺を左辺に代入する」くらいの意味）
STEP2の冒頭に戻る．
STEP3 終了
STEP2で$v_g$を取り出した場合は，最短距離およびその経路が確定しているのでそれを出力する．
OPENリストが空となった場合は，始点から終点への経路が存在しないことを出力する．