Dikjastra algorithm

dikjastra_maze.py

import heapq


def find_shortest_path_dijkstra(maze, start, end):
    """
    Find shortest path with dijkstra algorithm
    
    :param maze: List[List[int]]
    :param start: Tuple[int, int]
    :param end: Tuple[int, int]
    :return: List[Tuple[int, int]]
    """
    def get_neighbors(node, width, height):
        x, y = node
        neighbors = []
        if x > 0:
            neighbors.append((x - 1, y))
        if x < width - 1:
            neighbors.append((x + 1, y))
        if y > 0:
            neighbors.append((x, y - 1))
        if y < height - 1:
            neighbors.append((x, y + 1))
        return neighbors

    # Obtener las dimensiones del laberinto
    width = len(maze)
    height = len(maze[0])

    # Inicializar el conjunto de nodos visitados y no visitados
    visited = set()
    unvisited = [(0, start)]
    heapq.heapify(unvisited)

    # Inicializar el diccionario de costos de camino más corto
    cost_so_far = {start: 0}

    # Inicializar el diccionario de nodos anteriores en el camino más corto
    came_from = {}

    # Ejecutar el algoritmo de Dijkstra
    while unvisited:
        # Obtener el nodo no visitado con el costo más bajo
        current_cost, current_node = heapq.heappop(unvisited)

        # Si hemos encontrado el nodo final, terminar la búsqueda
        if current_node == end:
            break

        # Si el nodo actual ya ha sido visitado, pasar al siguiente nodo
        if current_node in visited:
            continue

        # Marcar el nodo actual como visitado
        visited.add(current_node)

        # Para cada vecino del nodo actual
        for x, y in get_neighbors(current_node, width, height):
            # Si el vecino es una pared, pasar al siguiente vecino
            if maze[x][y] == 0:
                continue

            # Calcular el costo de llegar al vecino desde el nodo actual
            new_cost = cost_so_far[current_node] + 1

            # Si aún no hemos visitado el vecino o si hemos encontrado un costo más bajo
            # para llegar al vecino, actualizar el costo y el nodo anterior
            if (x, y) not in visited or new_cost < cost_so_far.get((x, y), float('inf')):
                cost_so_far[(x, y)] = new_cost
                heapq.heappush(unvisited, (new_cost, (x, y)))
                came_from[(x, y)] = current_node

    # Reconstruir el camino más corto desde el nodo final hasta el inicio
    path = [end]
    while path[-1] != start:
        path.append(came_from[path[-1]])
    path.reverse()

    return path


if __name__ == "__main__":
    mat = [[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
           [1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
           [1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
           [0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
           [1, 1, 1, 0, 1, 1, 1, 0, 1, 0],
           [1, 0, 1, 1, 1, 1, 0, 1, 0, 0],
           [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
           [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
           [1, 1, 0, 0, 0, 0, 1, 0, 0, 1]]
    source = (0, 0)
    dest = (3, 4)

    dist = find_shortest_path_dijkstra(mat, source, dest)

    if dist != -1:
        print("Shortest Path is", dist)
    else:
        print("Shortest Path doesn't exist")

maze_generator.py

import random


def create_simple_binary_maze(width, height):
    """
    Generate a binary maze

    :param width: int
    :param height: int
    :return: List[List[int]]
    """
    maze = [[0 for y in range(height)] for x in range(width)]

    for x in range(width):
        for y in range(height):
            if x % 2 == 1 and y % 2 == 1:
                maze[x][y] = 1

    for x in range(1, width - 1, 2):
        for y in range(1, height - 1, 2):
            direction = None

            if x == 1:
                direction = random.choice(['down', 'right'])
            elif y == 1:
                direction = random.choice(['down', 'right'])
            elif x == width - 2:
                direction = random.choice(['up', 'right'])
            elif y == height - 2:
                direction = random.choice(['up', 'right'])
            else:
                direction = random.choice(['up', 'down', 'right'])

            if direction == 'up':
                maze[x][y-1] = 1
            elif direction == 'down':
                maze[x][y+1] = 1
            elif direction == 'right':
                maze[x+1][y] = 1

    return maze


if __name__ == "__main__":
    grid = create_simple_binary_maze(5, 5)

    for i in grid:
        print(i)