a-start path finding algorithm in python

Here's an implementation of the A-star algorithm in Python:


main.py
import heapq

def astar(graph, start, goal):
    frontier = []
    heapq.heappush(frontier, (0, start))
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while len(frontier) > 0:
        current = heapq.heappop(frontier)[1]

        if current == goal:
            break

        for next in graph.neighbors(current):
            new_cost = cost_so_far[current] + graph.cost(current, next)
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + graph.heuristic(next, goal)
                heapq.heappush(frontier, (priority, next))
                came_from[next] = current

    return came_from, cost_so_far
759 chars
26 lines