The A* Algorithm (A Star)
(from Elements of AI Using Common Lisp, by Tanimoto)

ALGORITHM A*
begin
   input the start node S and the GOAL (or set of GOALS);
   OPEN <- {S}; CLOSED <- NIL;
   g(S) <- 0; pred(S) <- NIL; found <- false;
   while OPEN is not empty and found is false do
   begin
      L <- the node on OPEN for which f is the least; 
                (or set of nodes if using a set of GOALS)
      if L is a singleton then let X be its sole element
      (NOTE: In our case, X is L because L is only one node)
      remove X from OPEN and put X into CLOSED;
      if X is a goal node then found <- true
      else begin
          generate the set SUCCESSORS of successors of X;
          for each Y in SUCCESSORS do
             if Y is not already on OPEN or on CLOSED then
             begin
                g(Y) <- g(X) + distance(X,Y);
                f(Y) <- g(Y) + h(y);
                pred(Y) <- X;
                insert Y in OPEN;
             end
             else begin /* Y is on OPEN or on CLOSED */
                Z <- pred(Y);
                temp <- f(Y) - g(Z) - distance(Z,Y) 
                               + g(X) - distance(X,Y);
                if temp < f(Y) then
                begin
                   g(Y) <- g(Y) - f(Y) + temp; /* UPDATE OPEN */
                   f(Y) <- temp;
                   pred(Y) <- X;
                   if Y is on CLOSED then /* UPDATE CLOSED */
                      insert Y on OPEN and remove Y from CLOSED;
                end;
             end;
        end; 
     end;  /* end while loop */