A* algorithm is a widely-used algorithm for path finding. Given a start node, it aims to find a path to a given goal with the smallest cost in a weighted graph. The basic idea of A* is to compute each node’s $f$ value and iteratively choose the node with the smallest f value to extend. The value $f$ of node $n$ is defines as follows:

where $g(n)$ is the cost of the path from the start node to node $n$, and $h(n)$ is the heuristic function to compute the estimated value of the cost from node $n$ to the goal, usually we use the Euclidean distance between two nodes to estimate $h(n)$.

To implement this algorithm, we usually have to maintain two lists. One is ‘open’ and the other is ‘closed’. Initially, the ‘open’ list only contains the start node and the ‘closed’ list is empty. At each iteration, we pop the node with the smallest $f$ value and extend its neighbors. For each neighbor node, if it is already in the ‘open’ list, update its f value everytime we get a smaller value, if it is not, add it to the ‘open’ list. After we have explored all the neighbors, we can then add the node to the ‘closed’ list which means we have done visiting this node.

Once our current node is the goal, we can stop since we have already find the path from the start node to the goal. If we want to find the whole path, we should also maintain a list of parents of each node so that we can backtrack from the goal to get the path.

// pseudocode
Astar:
	// initialize
	open = [start]
	closed = []  // empty list
	path = []
	parent = {}  // empty dictionary
	g = {}
	f = {}
	for each node in graph:
		g[node] = inf
		f[node] = inf
	g[start] = 0
	f[start] = g[start] + distance(start, goal)

	while open is not empty:
		current = node with the smallest f value in open
		// construct path
		if current == goal:
			path.append(current)
			while current in parent.keys():
				current = parent[current]
				path.insert(0, current)
			break

		open.remove(current)
		closed.append(current)

		for each neighbor of current:
			if neighbor in close:
				continue

			gnew = g[current] + distance(current, neighbor)
			if gnew < g[neighbor]:
				parent[neighbor] = current
				g[neighbor] = gnew
				f[neighbor] = gnew + distance(neighbor, goal)
				if neighbor not in open:
					open.append(neighbor)