Implementation of iterative deepening A* (Star) Algorithm

#node              current node
#g                 the cost to reach current node
#f                 estimated cost of the cheapest path (root..node..goal)
#h(node)           estimated cost of the cheapest path (node..goal)
#cost(node, succ)  step cost function
#is_goal(node)     goal test
#successors(node)  node expanding function
V={}
E={}
V=({'A':7,'B':9,'C':6,'D':5,'E':6,'F':4.5,'H':4,'I':2,'J':3,'K':3.5,'G':0})
E=({('B','D'):2,('A','B'):4,('A','C'):4,('A','D'):7,('D','E'):6,('E','F'):5,('D','F'):8,('D','H'):5,('H','I'):3,('I','J'):3,('J','K'):3,('K','H'):3,('F','G'):5})
INFINITY=10000000
cameFrom={}
def h(node):
    return V[node]
def cost(node, succ):
    return E[node,succ]

def successors(node):
    neighbours=[]
    for item in E:
        if node==item[0][0]:
            neighbours.append(item[1][0])
    return neighbours

def reconstruct_path(cameFrom, current):
    total_path = [current]
    while current in cameFrom:
        current = cameFrom[current]
        total_path.append(current)
    return total_path
   
def ida_star(root,goal):
    global cameFrom
    def search(node, g, bound):
        min_node=None
        global cameFrom
        f = g + h(node)
        if f > bound:return f
        if node==goal:return "FOUND"
        minn = INFINITY
        for succ in successors(node):
            t = search(succ, g + cost(node, succ), bound)
            if t == "FOUND":return "FOUND"
            if t < minn:
                minn = t
                min_node=succ
        cameFrom[min_node]=node
        return minn
       
    bound= h(root)
    count =1
    while 1:
        print "itertion"+str(count)
        count+=1
        t = search(root, 0, bound)
        if t == "FOUND":
            print reconstruct_path(cameFrom, goal)
            return bound
        if t == INFINITY:return "NOT_FOUND"
        bound = t
  
print ida_star('A','G')
   

Implementation of A* algorithm in python

V={}
E={}
V=({'A':7,'B':9,'C':6,'D':5,'E':6,'F':4.5,'H':4,'I':2,'J':3,'K':3.5,'G':0})
E=({('B','D'):2,('A','B'):4,('A','C'):4,('A','D'):7,('D','E'):6,('E','F'):4.5,('D','F'):8,('D','H'):4,('H','I'):3,('I','J'):3,('J','K'):3,('K','H'):3,('F','G'):5})



INFINITY=10000000
def find_neighbours(node):
    neighbours=[]
    for item in E:
        if node==item[0][0]:
            neighbours.append(item[1][0])
    return neighbours
   


def reconstruct_path(cameFrom, current):
    total_path = [current]
    while current in cameFrom:
        current = cameFrom[current]
        total_path.append(current)
    return total_path
    #

def Astar(start, goal):
   
    current = start
    fScore={}
    gScore={}
   
   
   
   
    # The set of currently discovered nodes still to be evaluated.
    openSet = set()
    # The set of nodes already evaluated.
    closedSet = set()
    # Initially, only the start node is known.
    openSet.add(current)
   
    # For each node, which node it can most efficiently be reached from.
    # If a node can be reached from many nodes, cameFrom will eventually contain the
    # most efficient previous step.
    cameFrom ={}#the empty map

    # For each node, the cost of getting from the start node to that node.
    for node in V:
        gScore[node] = INFINITY #map with default value of Infinity
    # The cost of going from start to start is zero.
    gScore[start] = 0
    # For each node, the total cost of getting from the start node to the goal
    # by passing by that node. That value is partly known, partly heuristic.
    for node in V:
        fScore[node] = INFINITY #map with default value of Infinity
    # For the first node, that value is completely heuristic.
    fScore[start] = V[start]#heuristic_cost_estimate(start, goal)
   
    def heuristic_cost_estimate(node, goal):
    return E[cameFrom[node],node]+V[node]
    count=0
    while openSet:
        count+=1
        if count>10:
            break
        print openSet
        minn=INFINITY
        for node in openSet:
            if fScore[node]<minn:
                current=node
        if current==None:
            current=start
        #current = node in openSet having the lowest fScore[] value)
        if current == goal:
            return reconstruct_path(cameFrom, goal)

        openSet.remove(current)
        #Add it to the closed set
        closedSet.add(current)
        for neighbor in find_neighbours(current):
            if neighbor in closedSet:
                continue        # Ignore the neighbor which is already evaluated.
            # The distance from start to goal passing through current and the neighbor.
            tentative_gScore = gScore[current] + E[(current, neighbor)]
            if neighbor not in openSet:    # Discover a new node
                openSet.add(neighbor)
            elif tentative_gScore >= gScore[neighbor]:
                continue        # This is not a better path.

            # This path is the best until now. Record it!
            cameFrom[neighbor] = current
            gScore[neighbor] = tentative_gScore
            fScore[neighbor] = gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)

    return "failure"



print Astar('A','K')