A* algorithm

Procedure

A-STAR(G, s, t, HEURISTIC)
    INITIALIZE-SINGLE-SOURCE-WITH-CONSTRAINT(G, s, HEURISTIC)
    S = ∅
    Q = G.Snt // ordered by the constraint
    
    while u ≠ t and Q ≠ ∅:
        u = EXTRACT-MIN(Q)
        S = S ∪ {u}
        for each vertex v in G.Adj[u]:
            RELAX(u, v, w, HEURISTIC)

INITIALIZE-SINGLE-SOURCE-WITH-CONSTRAINT(G, s, HEURISTIC):
    for each vertex v ∈ G.V:
        v.d = ∞
        G.Snt[v] = ∞
        v.π = NIL
    s.d = 0
    G.Snt[s] = HEURISTIC(s,t)

RELAX(u, v, w, HEURISTIC)
    if v.d > u.d + w(u, v):
        v.d = u.d + w(u, v)
        G.Snt[v] = v.d + HEURISTIC(v,t)
        v.π = u