edge_length={'a':{'b':6,'d':6},
             'b':{'a':6,'c':5,'e':10},
             'c':{'b':5,'d':6,'f':7},
             'd':{'a':6,'c':6,'h':4},
             'e':{'b':10,'f':6},
             'f':{'c':7,'e':6,'h':6},
             'h':{'d':4,'f':6, 'g':3},
             'g':{'h':3}
    }
def add_vertex(v, heu):
    if v in graph:
        print("vertex exists")
    else:
        graph[v] = []
        heuristic[v] = heu

def add_edges(v1, v2):
    if v1 not in graph or v2 not in graph:
        print("vertex not present")
    else:
        graph[v1].append(v2)
        graph[v2].append(v1)

def find_small(heuristic, curr, edge, cost):
    smallest = graph[curr][0]
    for i in graph[curr]:
        if cost+edge[curr][smallest]+heuristic[smallest] > cost+edge[curr][i]+heuristic[i]:
            smallest = i
    cost = cost+edge[curr][smallest]
    return smallest, cost

def astar(edge, heuristic, start, end):
    curr_node = start
    cost = 0
    visited = []
    while curr_node != end:
        if curr_node not in visited:
            visited.append(curr_node)
            small, cost = find_small(heuristic, curr_node, edge, cost)
            curr_node = small
    visited.append(curr_node)
    return visited, cost
graph = {
    'a':['b','d'],
       'b':['a','c','e'],
       'c':['b','d','f'],
       'd':['a','c','h'],
       'e':['b','f'],
       'f':['c','e','h'],
       'h':['d','f','g'],
       'g':['h'],
         }
heuristic = {
    'a':12,
     'b':19,
     'c':10,
     'd':6,
     'e':14,
     'f':4,
     'h':3,
     'g':0}
'''add_vertex("A", 4)
add_vertex("B", 8)
add_vertex("C", 3)
add_vertex("D", 0)
add_vertex("E", 5)

add_edges("A", "B")
add_edges("B", "E")
add_edges("A", "C")
add_edges("C", "D")
add_edges("E", "D")
add_edges("A", "D")'''
print(heuristic)
print(graph)
print(astar(edge_length, heuristic, 'b', 'g'))