问题描述:

Consider the following pseudocode for the `A* search algorithm`

:

`A*(G, s, h)`

for each vertex u in V

d[u] := f[u] := infinity

color[u] := WHITE

p[u] := u

end for

color[s] := GRAY

d[s] := 0

f[s] := h(s)

INSERT(Q, s)

while (Q != Ø)

u := EXTRACT-MIN(Q)

for each vertex v in Adj[u]

if (w(u,v) + d[u] < d[v])

d[v] := w(u,v) + d[u]

f[v] := d[v] + h(v)

p[v] := u

if (color[v] = WHITE)

color[v] := GRAY

INSERT(Q, v)

else if (color[v] = BLACK)

color[v] := GRAY

INSERT(Q, v)

end if

else

...

end for

color[u] := BLACK

end while

Now - do I understand correctly that if **we want to find a path from the source vertex ( s) to some destination vertex (let's name it d)** then we can simply

`u := EXTRACT-MIN(Q)`

statement like this: `u := EXTRACT-MIN(Q)`

if (u = d) RETURN PATH

This is obviously correct in case we don't need to reopen vertices (`else if (color[v] = BLACK`

), but ** is it correct** in case

This is correct. If you find the destination node, then you'll never have to reopen anything; you can just return the path. By the properties of the A* algorithm (including an admissible heuristic), the first time you pop the destination node off the priority queue, you'll have a shortest path to it.