How algorithm A* can find paths in a graph?
The algorithm receives:
- the graph
- the initial node
- the final node
- a function of heuristics
Starting from the initial node, it takes all the neighbors of the current node and applies the heuristic function. This function returns a number that indicates what is the pro node distance (usually used Euclidean distance). The neighbor that has the lowest value is the closest to the final node, then that neighbor becomes the current node. The same procedure is repeated until the current node is the final node.
It is restricted to a specific type of graph?
No. As I explained above, it is necessary to take all the neighboring nodes of the current one. In a directed graph are all nodes "leaving" the current; in an undirected graph are all nodes attached to the current.
How it determines the cost between the connected edges in the vertices of the graph?
This is done by the heuristic function. This function is very important, as it will direct the search to the right path. This depends entirely on how your graph is done, there is no "universal rule" of how to create the heuristic function. It needs to receive by parameter two nodes of the graph and return a number indicating how far these two nodes are.
For example: If the graph represents a 2D square labyrinth, the cell indices represented by the node can be used to calculate the distance. The distance between the cell nodes (1, 1) and (5, 4) may be calculated by the formula of euclidean distance.
Is there any mathematical formula used in this algorithm? If so, which one?
This obviously varies from graph to graph. It is your responsibility to understand how the graph is formed to discover a mathematical formula for the heuristic function.
What kind of data structure does it use?
A graph can be represented in several ways. The most common are using two nested hashmaps or with a 2D matrix. The A* algorithm itself is usually used with sets and hashmaps. (It has a example implementation on Wikipedia in English).