Python – A Star Search in Graph

A* is probably my favourite graph search algorithm. Some 10+ years ago, I have implmented it with Excel and after that I have written a few more implementations. Just, not to repeat myself, I will not discuss it here. The reason for this article is the set of videos in YouTube, that I have started about Graph Algorithms. Thus, A* had to be presented there.

This article contains some of the other articles and nice music, seeing the code just working by itself in Excel:

VBA – A* Search Algorithm with Excel

The implementation in Python, actually steps upon the Dijkstra algorithm and changes it a bit. The code itself is here:

def solve_a_star(data):
    lines = data.strip().split("\n")
    n_edges = int(lines[0].split()[1])
    edge_lines = lines[1:1 + n_edges]
    node_lines = lines[1 + n_edges: -1]
    
    start, end = lines[-1].split()
    
    graph = {}
    heuristics = {}

    for line in node_lines:
        edge_name, heuristic_weight = line.split()
        heuristics[edge_name] = int(heuristic_weight)

    for line in edge_lines:
        u, v, w = line.split()
        if u not in graph:
            graph[u] = []
        graph[u].append((v, int(w)))

    start_f = 0 + heuristics.get(start, 0)
    pq = [(start_f, start)]
    cost_so_far = {start: 0}
    came_from = {start: None}

    #A-star = g + h
    while pq:
        current_f, current_node = heapq.heappop(pq)

        if current_node == end:
            #Success!
            break

        best_known_g = cost_so_far[current_node]
        best_known_f = best_known_g + heuristics.get(current_node, 0)
                
        if current_f > best_known_f:
            continue
    
        for n, weight in graph.get(current_node, []): #n for neighbor
            new_g = cost_so_far[current_node] + weight

            if new_g < cost_so_far.get(n, float('inf')):
                cost_so_far[n] = new_g
                came_from[n] = current_node

                #highlight of A*:
                new_f = new_g + heuristics.get(n, 0)
                heapq.heappush(pq, (new_f, n))
    
    path = []
    if end in came_from:
        current = end
        while current:
            path.append(current)
            current = came_from[current]
        path.reverse()

    return path, cost_so_far

The GitHub with the Jupyter Notebook and the complete input is there – https://github.com/Vitosh/Python_personal/blob/master/YouTube/048_Python-Graph/048-Graph-A-Star.ipynb

Thanks and enjoy! 🙂