A* is the graph search and traversal algorithm that makes use of some additional function that decreases when we are approaching the goal node in the graph.Dijkstra algorithm is a separate case of A* algorithm where heuristic function is always zero (0).
Same as Dijkstra algorithm, the algorithm assigns the "distance value" to every node. This value is the distance (cost) to reach the node from the initial (starting) node. This value is of course zero for the initial node itself. At the start of the algorithm, it is set to be infinite for all other nodes in the graph. The algorithm also needs to remember the collection of already visited nodes. The "current node" is initially set to the initial node.
The algorithm can be implemented as following:
The algorithms terminates when the goal node becomes the current node. The found path is not stored in the algorithm data structures and must be separately recorded. If the algorithm works as expected, it visits only part of all nodes in the graph (nodes that are clearly not in the shortest patch are not visited).
This algorithm is similar to the algorithm of the car driver that prefers roads bringing him geographically closer to the goal. This usually works well enough in the real world roads. Surely it is possible to imagine "traps" when it is not possible to cross some obstacle close to the goal and it is necessary to return back searching for another way, but this is not frequent.
In the worst case the algorithm running time is exponential to the length of the existing shortest path, but under some better circumstances it should be polynomial. If the h(n) is useful, it should outperform the plain Dijkstra search algorithm.
A* is a breadth first algorithm and as such consumes huge memory to keep the data of current proceeding nodes . The search can be more efficient if the machine searches not just for the path from the source to the target, but also in parallel for the path from the target to the source (the answer is found when these two searches meet at some point).