A* algorithm

The A* algorithm aims to find optimal paths through a graph. It is more efficient than Dijkstra’s algorithm, avoiding the exploration of every individual path. It does so by associating with each node $i$ the values:

• $f_i$, the “cost” of the path so traversed so far.
• $h_i$, an estimate of the “cost” left before we reach the destination.

Info

Dijkstra’s algorithm equals A* algorithm by setting $h_i=0$ for all nodes $i$.

stateDiagram-v2
	[*] --> start
	start: Initialize our starting point as the only node to explore
	node_selection: Select the unexplored node N with the least f+g
	node_generation: Generate all neighbours of N, adding them to the unexplored nodes
	node_processing: Add the generated nodes to the unexplored node list, with the associated f and g values.
	current_node_processing: Move the current node to the processed nodes list, with the associated path
	destination_reached: Is one of our unexplored nodes our target?
	return_path: Return the associated path as the answer

	state destination_reached_q <<choice>>


    start --> node_selection
    state node_selection{
	    [*] --> node_generation
	    node_generation --> node_processing
	    node_processing --> current_node_processing
	    current_node_processing --> [*]
	}

	node_selection --> destination_reached
	destination_reached --> destination_reached_q
	destination_reached_q --> return_path: Yes
	destination_reached_q --> node_selection: No
	return_path --> [*]