ExpNo 4 : Implement A* search algorithm for a Graph

Name: THIRUMALAI K

Register Number: 212224240176

Aim:

To ImplementA * Search algorithm for a Graph using Python 3.

Algorithm:

// A* Search Algorithm
1.  Initialize the open list
2.  Initialize the closed list
    put the starting node on the open 
    list (you can leave its f at zero)

3.  while the open list is not empty
    a) find the node with the least f on 
       the open list, call it "q"

    b) pop q off the open list
  
    c) generate q's 8 successors and set their 
       parents to q
   
    d) for each successor
        i) if successor is the goal, stop search
        
        ii) else, compute both g and h for successor
          successor.g = q.g + distance between 
                              successor and q
          successor.h = distance from goal to 
          successor (This can be done using many 
          ways, we will discuss three heuristics- 
          Manhattan, Diagonal and Euclidean 
          Heuristics)
          
          successor.f = successor.g + successor.h

        iii) if a node with the same position as 
            successor is in the OPEN list which has a 
           lower f than successor, skip this successor

        iV) if a node with the same position as 
            successor  is in the CLOSED list which has
            a lower f than successor, skip this successor
            otherwise, add  the node to the open list
     end (for loop)
  
    e) push q on the closed list
    end (while loop)

PROGRAM :

from collections import defaultdict

H_dist = {}

def aStarAlgo(start_node, stop_node):
    open_set = set(start_node)
    closed_set = set()
    g = {}               # store distance from starting node
    parents = {}         # parents contains an adjacency map of all nodes

    g[start_node] = 0
    parents[start_node] = start_node

    while len(open_set) > 0:
        n = None

        # node with the lowest f() = g(n) + h(n)
        for v in open_set:
            if n is None or g[v] + heuristic(v) < g[n] + heuristic(n):
                n = v

        # If no node found (shouldn’t usually happen)
        if n is None:
            print("Path does not exist!")
            return None

        # If goal reached, reconstruct path
        if n == stop_node:
            path = []
            while parents[n] != n:
                path.append(n)
                n = parents[n]
            path.append(start_node)
            path.reverse()
            print('Path found: {}'.format(path))
            return path

        # Explore neighbors
        for (m, weight) in get_neighbors(n):
            if m not in open_set and m not in closed_set:
                open_set.add(m)
                parents[m] = n
                g[m] = g[n] + weight
            else:
                if g[m] > g[n] + weight:
                    g[m] = g[n] + weight
                    parents[m] = n
                    if m in closed_set:
                        closed_set.remove(m)
                        open_set.add(m)

        open_set.remove(n)
        closed_set.add(n)

    print('Path does not exist!')
    return None


# FIXED FUNCTION 1: Get neighbors of a node
def get_neighbors(v):
    """
    Retrieves a value from the Graph_nodes dictionary based on the provided key.
    Returns the list of (neighbor, cost) pairs if found, otherwise None.
    """
    if v in Graph_nodes:
        return Graph_nodes[v]
    else:
        return None


# FIXED FUNCTION 2: Heuristic function
def heuristic(n):
    return H_dist[n]

graph = defaultdict(list)
n, e = map(int, input().split())

for i in range(e):
    u, v, cost = map(str, input().split())
    cost = float(cost)
    graph[u].append((v, cost))
    graph[v].append((u, cost))  # undirected graph

for i in range(n):
    node, h = map(str, input().split())
    H_dist[node] = float(h)

print("Heuristic Distances:", H_dist)
Graph_nodes = graph
print("Graph:", dict(graph))

aStarAlgo('A', 'J')

---

Sample Graph I

---

---

Sample Input

---

10 14
A B 6
A F 3
B D 2
B C 3
C D 1
C E 5
D E 8
E I 5
E J 5
F G 1
G I 3
I J 3
F H 7
I H 2
A 10
B 8
C 5
D 7
E 3
F 6
G 5
H 3
I 1
J 0

---

Sample Output

---

Path found: ['A', 'F', 'G', 'I', 'J']

OUTPUT:

---

Sample Graph II

---

---

Sample Input

---

6 6
A B 2
B C 1
A E 3
B G 9
E D 6
D G 1
A 11
B 6
C 99
E 7
D 1
G 0

---

Sample Output

---

Path found: ['A', 'E', 'D', 'G']

OUTPUT :

RESULT :

Sccessfully implemented A* search algorithm for a Graph