A* search algorithm: graph search algorithms in C

Select LanguageAfrikaansAlbanianArabicArmenianAzerbaijaniBasqueBelarusianBulgarianCatalanChinese (Simplified)Chinese (Traditional)CroatianCzechDanishDutchEnglishEstonianFilipinoFinnishFrenchGalicianGeorgianGermanGreekHaitian CreoleHebrewHindiHungarianIcelandicIndonesianIrishItalianJapaneseKoreanLatvianLithuanianMacedonianMalayMalteseNorwegianPersianPolishPortugueseRomanianRussianSerbianSlovakSlovenianSpanishSwahiliSwedishThaiTurkishUkrainianUrduVietnameseWelshYiddishBengaliGujaratiMarathiNepaliPunjabiTamilTelugu

 

A * algorithm is a searching algorithm that searches for the shortest path between the  

initial and the final state. It is used in various applications, such as maps.

Searching Algorithm follows two technique such as

• Bfs(Breadth First Search)

• Dfs(Depth First Search)

Breadth First Search is a vertex based technique for finding the shortest path in a graph. It 

uses a Queue data structure which follows first in first out. In BFS, one vertex is selected at a 

time when it is visited and marked then its adjacent are visited and stored in the queue. It is 

slower than DFS.

Depth First Search is an edge based technique. It uses the Stack data Structure, performs two

 stages, first visited vertices are pushed into stack and second if there are number vertices then 

visited vertices are popped.

Example :

BFs output : A , B , C , D , E , F DFs output : A , B , D , C , E , F

The A* search algorithm is an extension of Dijkstra's algorithm useful for finding the lowest cost 

path between two nodes of a graph. The path may traverse any number of nodes connected by 

edges with each edge having an associated cost. The algorithm uses a heuristic which 

associates an estimate of the lowest cost path from this node to the goal node, such that this 

estimate is never greater than the actual cost.

A * algorithm works :

Imagine a square grid which possesses many obstacles, scattered randomly. The initial and the 

final cell is provided. The aim is to reach the final cell in the shortest amount of time.

Explanation

A* algorithm has 3 parameters:

• g : the cost of moving from the initial cell to the current cell. Basically, it is the sum of all 

  the cells that have been visited since leaving the first cell.

• h : also known as the heuristic value, it is the estimated cost of moving from the current 

  cell to the final cell. The actual cost cannot be calculated until the final cell is reached. 

  Hence, h is the estimated cost. We must make sure that there is never an over 

  estimation of the cost.

• f : it is the sum of g and h. 

So,   f = g + h

The way that the algorithm makes its decisions is by taking the f-value into account. The 

algorithm selects the smallest f-valued cell and moves to that cell. This process continues until 

the algorithm reaches its goal cell.

 

Example:

A* algorithm is very useful in graph traversals as well. In the following slides, you will see how 

the algorithm moves to reach its goal state.

Suppose you have the following graph and you apply A* algorithm on it. The initial node is A 

and the goal node is E.

At every step, the f-value is being re-calculated by adding together the g and h values. The 

minimum f-value node is selected to reach the goal state. Notice how node B is never visited.

 

 

Steps:

	Source : visit node A  Destination : node E Adjacent node of A : B and C
	Visit adjacent node of A : B and C Compare the destination node :  (B==E) =>False (C==E) =>False Cost of (A->B) : 2 Cost of (A->C) : 1 Compare to distance : (A->B) > (A->C) min= (A->C) =1
	Visit adjacent node of C : D Compare the destination node : (D==E) =>False Cost of (C->D) : 1 min=(A->C) + (C->D) min = 1+1=2
	Visit adjacent node of D : E Cost of (D->E) : 1 min= (A->C) +( C->D) + (D->E) min=1+1+2=4 Compare the destination node : (E==E) =True Cost of (A->E)=min=4 Minimum Path= A->C->D->E

Algorithm:

Implementation of Dijikstra’s algorithm for finding the shortest path between two nodes in a 

weighted graph represented by a weight matrix and also using adjacency list

 n : Number of nodes in the graph

s : Source

t : Destination 

*pd : Shortest distance

precede[i] : Shortest path 

Steps :

for(all nodes i)

{

    distance[i] = INFINITY;

    perm[i] = NONMEMBER;

}

perm[s]=MEMBER;

distance[s]=0;

current=s;

while(current != t)

{

    dc = distance[current];

    for(all nodes i that are successors of current)

    {

        newdist = dc + weight[current][i];

        if(newdist < distance[i])

        {

            distance[i] = newdist;

            precede[i] = current;

        }

    }

k = the node k such that perm[k] == NONMEMBER and

    Such that distance[k] is smallest;

current = k;

perm[k] = MEMBER;

 }

*pd = distance[t];

Authored by: Manjula sharma.