New way of doing the A* Algorithm I wrote a Python script for implementing an A* algorithm. Map, Start and Goal are given.

The code works well as far as I tested it but I want to get feedback from the best out there too. So I am sharing the code here. Map is given to you as pickle file.

In the code M is:

class Map:
    def __init__(self, G):
        self._graph = G
        self.intersections = networkx.get_node_attributes(G, "pos")
        self.roads = [list(G[node]) for node in G.nodes()]

Graph = pickle.load(pickleFile)    
M = Map(Graph)


Start/Goal are two integers representing nodes.

def shortest_path(M, start, goal):
    explored = set([start])
    frontier = dict([(i,[start]) for i in M.roads[start]]) if start!=goal else {start:[]}
    while frontier:
        explore = g_h(frontier,goal,M)
        for i in [i for i in M.roads[explore] if i not in frontier.keys()|explored]:
            frontier[i]=frontier[explore]+[explore]
        frontier = cleanse_frontier(frontier,M)
        if explore==goal:return frontier[explore]+[explore]#break when goal is explored.               
        explored.add(explore)
        del frontier[explore]#once explored remove it from frontier. 

def g_h(frontier,goal,M):
    g_h = dict([(path_cost(frontier[node]+[node],M)+heuristic(node,goal,M),node) for node in frontier])  
    return g_h[min(g_h)]

def heuristic(p1,p2,M):#Euclidean Heuristic from the node to the goal node
    M=M.intersections 
    return ((M[p1][0]-M[p2][0])**2+(M[p1][1]-M[p2][1])**2)**0.5

def path_cost(path,M,cost=0):#Euclidean distance for the path
    M=M.intersections 
    for i in range(len(path)-1):
        cost += ((M[path[i]][0]-M[path[i+1]][0])**2+(M[path[i]][1]-M[path[i+1]][1])**2)**0.5
    return cost

def cleanse_frontier(frontier,M):
    """If any node can be removed from the frontier if that can be reached 
    through a shorter path from another node of the frontier, remove it 
    from frontier"""
    for node in list(frontier):
        for i in [i for i in frontier if i!=node]:
            if node not in frontier:continue                
            if frontier[i]==frontier[node]:continue
            if i not in M.roads[node]:continue
            if path_cost(frontier[node]+[node]+[i],M)&lt;path_cost(frontier[i]+[i],M):
                del frontier[i]
    return frontier
A suggestion I have is to use a heap data structure to store the costs, so that min can be calculated in logarithmic time.