Python, Dijkstra 算法可视化

Question

我正在尝试在 python 中可视化 Dijkstra 算法，其中每个节点都是一个正方形 - 请参见下图。但感觉有点不对劲。我将最短路径的结果与标准 A* 进行了比较，但我没有得到完全相同的路径。我认为我的代码已关闭，但我不知道具体情况如何。

我正在使用 PriorityQueue

网格是对象列表的列表 -

每个对象代表屏幕上的一个立方体-

draw - 将网格绘制到屏幕上

** -code- ** 中的代码是我在发布问题后编辑的部分。


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，我感到很抱歉，我试图在我去的时候评论我的想法，我希望它是可以理解的。

Answer 1

为进入 PQ 的元素添加一个计数器可以将所有内容分类。 PQ.put((0, counter, start))，计数器在程序开始时从零开始，每次我们将一个元素放入 PQ（最后一个 if 语句）时，我们都会增加计数器，从而减少优先级。

Python, Dijkstra 算法可视化

Python, Dijkstra's Algorithm visualization

python

shortest-path

dijkstra