A Star Algorithm Work

A * or A-star algorithm is another basic for finding shortest path in a graph. This algorithm is used in maps or games a lot.

There are three different parameters are used to find the shortest path using A* or A-star algorithm. These are called g, h, f. Let's see their definition

g: This is used for finding the cost from initial node to the current node. As we traverse through the nodes, this value always gets increased since this is the summation of all the previous costs.

h: This is used to describe the cost from the corrent node to the final or goal node. This values always gets decreased as we move from the current node to goal node.

f: This is the total cost for going to the final node. This is the summation of the previous two parameters. So f = g + h

Since g and h are always changable during the traversal, f is always changable. So we have to recalculate f all the time.

Let's see in detail how it works.

From the above video you see that we reach from node A to node E. 

From A to C the f value is 3, but from A to B the f value is 4. So A to C path is choosen as shortest path. When we start from node A to C, the current cost 1 that is g value, and from C to E the value is 2, so total f value at node C is 1+2=3.

But from node A to B the value is 2+2=4. So this node path is not choosen.