Блог

Я пытаюсь визуализировать алгоритм Дейкстры в python, где каждый узел представляет собой квадрат — см. Рисунок ниже. но что-то здесь не так. Я сравнил результат кратчайшего пути со стандартным A* и получил не совсем тот же путь. Я думаю, что мой код отключен, но я не понимаю, как именно.

Я использую приоритетную очередь

сетка-это список списков объектов —

каждый объект представляет собой куб на экране-

рисовать — рисует сетку на экране

код внутри ** -код — * * — это часть, которую я отредактировал после публикации вопроса.

 
def dijkstra_algorithm(grid, start, end):
    # set up dist (distance to start) with infinity
    dist = {elem: float("inf") for row in grid for elem in row}

    # distance from start to start is 0.
    dist[start] = 0

    # set up prev dict - prev[V] = U - represents that the shortest current path to X is through U
    prev = {}

    # create Priority Queue based on distance from origin and insert start to PQ
    PQ = PriorityQueue()
    counter = 0
    # create hash table to check if element is inside PQ.
    PQ.put((0, counter, start))
    PQ_hash = {start}

    # insert every elem except start into PQ with distance infinity
    for row in grid:
        for elem in row:
            if elem != start:
                PQ.put((dist[elem],**float("inf")**, elem))
                PQ_hash.add(elem)


    # iterate untill PQ is empty
    while not PQ.empty():
        

        current = PQ.get()[1]  # get element with min distance - index 1 in (dist[elem], elem)

        # if what's left is infinitly far - there is no path from start to end
        if dist[current] == float('inf'):
            return False

        PQ_hash.remove(current)  # remove element from Hash table (PQ.get removes elem from PQ)
        current.set_closed() #(color - red)
        draw_func() #(draw the grid)
              
        if current == end: #end node found

            reconstruct_path(prev, current, draw_func) #draw path from end to start
            end.set_end()
            start.set_start()
            return True # found

        #iterate over all neighbors of current node

        for neighbor in current.neighbors:
            # if neighbor inside PQ

            if neighbor in PQ_hash: 
                #calculate distance if we go to neighbor through current ( 1 distance)
                alt = dist[current]   1

                #if quicker - update
                if alt < dist[neighbor]:
                    dist[neighbor] = alt
                    prev[neighbor] = current
                  **counter  = 1 **
                    PQ.put((dist[neighbor],**counter**, neighbor))
                    neighbor.set_open() #color green
                    draw_func() #draw the grid
    #path not found
    return False
 

Я думаю, что это как-то связано с тем, что я добавляю в PQ вместо редактирования, но я не уверен.
Кроме того, я сожалею об отсутствии PEP8, я пытался прокомментировать свои мысли по ходу, надеюсь, это понятно.

Добавление счетчика к элементам, которые входят в PQ, все упорядочивает. PQ.put((0, счетчик, начало)), счетчик начинается с нуля в начале программы, и каждый раз, когда мы помещаем элемент в PQ (последний оператор if), мы увеличиваем счетчик, тем самым уменьшая приоритет.