Converting Dijkstra to A star algorithm in python

Question

I am trying to convert a dijkstra min heap (priority queue) algo to an a* with heuristics - the dijkstra algorithm I'm adapting is here: https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/

Is the below algorithm a correct implementation of a_star ? It worked for me on a couple test graphs

If f = g + h, then I have modified the priority queue to store the tuple: (f, g, vertex ) per @btilly comment below - so it will pull the lowest f_distance on each heappop() I have also added the visited set.

import heapq

# V+ElogE time / E space
def a_star(graph, start, dest, heuristic):
    distances = {vertex: float('inf') for vertex in graph} # V time / V space
    distances[start] = 0

    parent = {vertex: None for vertex in graph} # store path => V time / V space

    visited = set()

    pq = [( 0 + heuristic[start], 0 ,  start)] # E space

    while pq: # ElogE time
        curr_f, curr_dist, curr_vert = heapq.heappop(pq) #logE time

        if curr_vert not in visited:
            visited.add(curr_vert)

            for nbor, weight in graph[curr_vert].items():
                distance = curr_dist + weight  # distance from start (g)
                f_distance = distance + heuristic[nbor] # f = g + h

                # Only consider this new path if it's f_distance is better
                if f_distance < distances[nbor]:
                    distances[nbor] = f_distance
                    parent[nbor] = curr_vert


                    if nbor == dest:
                        # we found a path based on heuristic
                        return distances, parent

                    heapq.heappush(pq, (f_distance, distance, nbor)) #logE time

    return distances, parent


graph = {
    'A': {'B':3, 'H':4, 'F': 1},
    'B': {'A': 3, 'C':5  },
    'C': {'B':5, 'D':6, 'I':2},
    'D': {'C':6, 'E':1},
    'E': {'D':1, 'I':2, 'G':20},
    'F': {'A':1, 'G':1},
    'G': {'F':1, 'E':20},
    'H': {'A':4, 'I':8, },
    'I': {'H':8, 'C':2, 'E':2},
}
heuristic = {
    'A': 20,
    'B': 19,
    'C': 16,
    'D': 12,
    'E': 0,
    'F': 13,
    'G': 11,
    'H': 15,
    'I': 10,
}


start = 'A'
dest= 'E'
distances,parent = a_star(graph, start, dest, heuristic)

Answer 1

Here's the full code to generate the path . The graph is based on this youtube:

path => A->B->D->K->P

import heapq

# V+ElogE time / E space
def a_star(graph, start, dest, heuristic):
    distances = {vertex: float('inf') for vertex in graph} # V time / V space
    distances[start] = 0

    parent = {vertex: None for vertex in graph} # store path => V time / V space

    visited = set()

    pq = [( 0 + heuristic[start], 0 ,  start)] # E space

    while pq: # ElogE time
        curr_f, curr_dist, curr_vert = heapq.heappop(pq) #logE time


        if curr_vert not in visited:
            visited.add(curr_vert)

            for nbor, weight in graph[curr_vert].items():
                distance = curr_dist + weight  # distance from start (g)
                f_distance = distance + heuristic[nbor] # f = g + h

                # Only process new vert if it's f_distance is lower
                if f_distance < distances[nbor]:
                    distances[nbor] = f_distance
                    parent[nbor] = curr_vert


                    if nbor == dest:
                        # we found a path based on heuristic
                        return distances, parent

                    heapq.heappush(pq, (f_distance, distance, nbor)) #logE time

    return distances, parent



def generate_path_from_parents(parent, start, dest):
    path = []
    curr = dest
    while curr:
        path.append(curr)
        curr = parent[curr]

    return '->'.join(path[::-1])



# FROM https://www.youtube.com/watch?v=eSOJ3ARN5FM&list=PLTd6ceoshprfgFGcdiQw9LQ3fXaYC-Zs2&index=3
graph = {
    'A': {'B':5, 'C':5},
    'B': {'A':5, 'C':4, 'D':3  },
    'C': {'A':5, 'B':4, 'D':7, 'E':7, 'H':8},
    'D': {'B':3, 'C':7, 'H':11, 'K':16, 'L':13, 'M':14},
    'E': {'C':7, 'F':4, 'H':5},
    'F': {'E':4, 'G':9},
    'G': {'F':9, 'N':12},
    'H': {'E':5, 'C':8, 'D':11, 'I':3 },
    'I': {'H':3, 'J':4},
    'J': {'I':4, 'N':3},
    'K': {'D':16, 'L':5, 'P':4, 'N':7},
    'L': {'D':13, 'M':9, 'O':4, 'K':5},
    'M': {'D':14, 'L':9, 'O':5},
    'N': {'G':12, 'J':3, 'P':7},
    'O': {'M':5, 'L':4},
    'P': {'K':4, 'J':8, 'N':7},
}


heuristic = {
    'A': 16,
    'B': 17,
    'C': 13,
    'D': 16,
    'E': 16,
    'F': 20,
    'G': 17,
    'H': 11,
    'I': 10,
    'J': 8,
    'K': 4,
    'L': 7,
    'M': 10,
    'N': 7,
    'O': 5,
    'P': 0
}

start = 'A'
dest= 'P'
distances,parent = a_star(graph2, start, dest, heuristic2)
print('distances => ', distances)
print('parent => ', parent)
print('optimal path => ', generate_path_from_parents(parent,start,dest))