Does the A* algorithm visit every node?

Question

I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, appear to show the algorithm stopping after finding the first path as the white blocks spreading out on the linked video do not cover the whole area before the path is highlighted, implying that not all nodes are visited.

Does the algorithm, therefore, not visit every node and instead stop after the first path is found? If so, is it not possible that a more optimum path could exist than the one found?

Answer 1

It depends on how you implement your heuristic function. There are some properties that it must satisfy so that it will indeed return the optimal (shortest) path.

$A^*$ differs from Dijkstra in the order that it chooses to expand partial paths. Recall that $A^*$ expands a partial path to node $x$ if $f(x)$ is minimized over all nodes in the fringe. $$f(x) = g(x) + h(x)$$ where $g(x)$ is the actual distance to node $x$ and $h(x)$ is the heuristic estimate of the distance from $x$ to the goal node.

For $A^*$ to choose an optimal (shortest) path $h(x)$ must satisfy:

• $h(x)$ is admissible, meaning it never over-estimates the actual minimal cost of reaching the goal.
• If you do use a closed set, meaning you never revisit nodes when they have already been visited (a tree search algorithm), then $h(x)$ must also be monotonic / consistent. This means for any pair of adjacent nodes $(x,y)$ we must have: $$h(x) \leq d(x,y) + h(y)$$ In other words, it is impossible to decrease $f(x)$ by extending the path to include a neighboring node.

Dijkstra's Algorithm is a case of $A^*$ where $h(x) = 0$ and thus satisfies the listed properties and is therefore optimal.

Best-First Search is a case of $A^*$ where $h(x)$ often overestimates the minimal cost (depending on implementation) and thus is not admissible and is therefore non-optimal.

Answer 2

It only flood-fills the graph if there is no path to the end-node.

What would be the point of including a heuristic if you were just going to visit every node anyways?