Dijkstra and A star compared

import heapq

def reconstruct_path(came_from, current):
    """Reconstruct the path from start to current node."""
    path = []
    while current in came_from:
        path.append(current)
        current = came_from[current]
    return path[::-1]

def dijkstra(grid, start, end):
    """Dijkstra's algorithm to find the shortest path in a grid."""
    rows, cols = len(grid), len(grid[0])
    visited = set()
    came_from = {}
    queue = [(0, start)]
    explored_nodes = []

    while queue:
        current_dist, current = heapq.heappop(queue)
        if current in visited:
            continue
        visited.add(current)
        came_from[current] = None if current == start else prev
        explored_nodes.append(current)

        if current == end:
            return current_dist, reconstruct_path(came_from, current), explored_nodes

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            x, y = current[0] + dx, current[1] + dy
            prev = current
            if 0 <= x < rows and 0 <= y < cols and grid[x][y] == 0 and (x, y) not in visited:
                heapq.heappush(queue, (current_dist + 1, (x, y)))

    return -1, [], explored_nodes

def manhattan_distance(start, end):
    """Calculate the Manhattan distance between two points."""
    return abs(start[0] - end[0]) + abs(start[1] - end[1])

def a_star(grid, start, end):
    """A* algorithm to find the shortest path in a grid."""
    rows, cols = len(grid), len(grid[0])
    visited = set()
    came_from = {}
    queue = [(manhattan_distance(start, end), 0, start)]
    explored_nodes = []

    while queue:
        total_cost, current_dist, current = heapq.heappop(queue)
        if current in visited:
            continue
        visited.add(current)
        came_from[current] = None if current == start else prev
        explored_nodes.append(current)

        if current == end:
            return current_dist, reconstruct_path(came_from, current), explored_nodes

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            x, y = current[0] + dx, current[1] + dy
            prev = current
            if 0 <= x < rows and 0 <= y < cols and grid[x][y] == 0 and (x, y) not in visited:
                heapq.heappush(queue, (current_dist + 1 + manhattan_distance((x, y), end), current_dist + 1, (x, y)))

    return -1, [], explored_nodes

# Example grid and start/end points
grid = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 0, 1, 1, 1, 0],
    [0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 1, 1, 1, 0, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 1, 1, 1, 0]
]
start = (0, 0)
end = (9, 9)

# Run both algorithms
dijkstra_result, dijkstra_path, dijkstra_explored = dijkstra(grid, start, end)
a_star_result, a_star_path, a_star_explored = a_star(grid, start, end)

print(f"Dijkstra: Path length = {dijkstra_result}")
print(f"A*      : Path length = {a_star_result}")

print(f"Dijkstra: Nodes explored = {len(dijkstra_explored)} Explored: {dijkstra_explored}")
print(f"A*      : Nodes explored = {len(a_star_explored)} Explored: {a_star_explored} ")