Python实现Dijkstra算法可视化与A*路径不一致问题求助

我尝试用Python实现Dijkstra算法可视化，每个节点对应一个网格方块（参考下图），但运行结果存在异常。我将计算得到的最短路径与标准A*算法的输出做了对比，二者路径并不完全一致，我认为代码存在错误但暂时无法定位具体问题点。

我使用了PriorityQueue作为优先队列。
grid是存储对象的嵌套列表，每个对象对应屏幕上的一个方块，draw方法负责将网格渲染到屏幕上，包裹的代码片段是我发布问题后编辑修改的部分。

原有实现代码：

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

我猜测问题可能和我直接向优先队列中新增元素而非修改原有元素的操作有关，但无法完全确定。另外抱歉代码未符合PEP8规范，我已尽可能添加注释说明思路，希望便于大家理解。

错误点梳理 #

• 优先队列元素解析错误：你定义的优先队列条目结构为(距离, 计数器, 节点)，但取当前节点时错误取了索引1的计数器值，而非索引2的节点对象，属于核心逻辑错误。
• 节点初始化插入参数错误：插入非起点节点时，第二个参数错误写入float("inf")，不符合预设的条目结构，导致优先队列排序完全失效。
• 重复元素处理逻辑冗余：Python标准库PriorityQueue不支持原位修改已有条目，你维护的PQ_hash判断逻辑完全不需要，插入新的更短距离条目后，旧条目只要在取出时校验距离有效性即可自动跳过。

修复后代码 #

from queue import PriorityQueue

def dijkstra_algorithm(grid, start, end, draw_func):
    # 初始化所有节点到起点的距离为无穷大
    dist = {elem: float("inf") for row in grid for elem in row}
    dist[start] = 0
    # 记录路径前驱节点
    prev = {}

    PQ = PriorityQueue()
    counter = 0
    # 仅插入起点，无需提前插入所有节点
    PQ.put((0, counter, start))

    while not PQ.empty():
        # 取出最短距离的条目，索引2为节点对象
        current_dist, _, current = PQ.get()

        # 当前取出的是无效旧条目，直接跳过
        if current_dist > dist[current]:
            continue
        
        # 剩余节点距离都是无穷大，无可达路径
        if dist[current] == float('inf'):
            return False

        current.set_closed() # 标记为已处理（红色）
        draw_func() # 渲染网格
              
        if current == end: # 找到终点
            reconstruct_path(prev, current, draw_func) # 回溯绘制路径
            end.set_end()
            start.set_start()
            return True

        # 遍历当前节点的所有邻居
        for neighbor in current.neighbors:
            alt = dist[current] + 1
            # 找到更短的路径
            if alt < dist[neighbor]:
                dist[neighbor] = alt
                prev[neighbor] = current
                counter += 1
                PQ.put((dist[neighbor], counter, neighbor))
                neighbor.set_open() # 标记为待处理（绿色）
                draw_func()
    # 无可达路径
    return False

补充说明 #

修复后如果最终路径和A算法输出的路径不完全一致属于正常情况：网格中如果存在多条长度相同的最短路径，Dijkstra和A的探索顺序不同，会返回不同的最短路径，只要路径长度一致即为正确结果。

内容的提问来源于stack exchange，提问作者Amit Davidi