Dijkstra 算法：我的实现有缺陷吗？

Question

为了在Python和图论两个方面训练自己，我尝试使用Python3实现Dijkstra算法，并提交给几个在线评委，看看是否正确.

在很多情况下效果很好，但并非总是如此。

例如，我卡在this one：测试用例工作正常，我也尝试了自己的自定义测试用例，但是当我提交以下解决方案时，法官一直告诉我"wrong answer"，预期的结果确实与我的输出大不相同。

请注意，法官针对相当复杂的图（10000 个节点和 100000 条边）对其进行测试，而我之前尝试的所有案例都没有超过 20 个节点和大约 20-40 条边。

这是我的代码。

给定 al 以下形式的邻接表：

al[n] = [(a1, w1), (a2, w2), ...]

哪里

n为节点id；
a1, a2, etc.是它的相邻节点，w1, w2, etc.是给定边的各自权重；

假设最大距离不超过 10 亿，我是这样实现 Dijkstra 算法的：

import queue

distance = [1000000000] * (N+1) # this is the array where I store the shortest path between 1 and each other node
distance[1] = 0 # starting from node 1 with distance 0

pq = queue.PriorityQueue()
pq.put((0, 1)) # same as above

visited = [False] * (N+1) 

while not pq.empty():
    n = pq.get()[1]
    if visited[n]:
        continue
    visited[n] = True
    for edge in al[n]:
        if distance[edge[0]] > distance[n] + edge[1]:
            distance[edge[0]] = distance[n] + edge[1]
            pq.put((distance[edge[0]], edge[0]))

你能帮我理解我的实现是否有缺陷，或者我只是运行进入了一些有问题的在线判断？

非常感谢。

更新

根据要求，我提供了用于填充链接问题的邻接列表 al 的代码段。

N,M = input().split()
N,M = int(N), int(M)

al = [[] for n in range(N+1)]

for m in range(M):
    try:
        a,b,w = input().split()
        a,b,w = int(a), int(b), int(w)
        al[a].append((b, w))
        al[b].append((a, w))
    except:
       pass

（请不要介意丑陋的 "except: pass"，我只是为了调试目的使用它...:P）

Answer 1

解读题中的主要问题：

根据您的解析代码，您将输入数据视为无向图，即从 A 到 B 的每条边也是从 B 到 A 的边。似乎这个前提是无效的，它应该是一个有向图，即你必须删除这一行：

    al[b].append((a, w))  # no back reference!

之前的问题，现在已经在代码中修复：

目前，您正在使用队列中边的永不改变的权重：

        pq.put((edge[1], edge[0]))

这样，节点总是在队列中的相同位置结束，无论在算法的哪个阶段以及到达该节点的路径实际有多远。相反，您应该使用到目标节点的新距离 edge[0]，即 distance[edge[0]] 作为队列中的优先级：

        pq.put((distance[edge[0]], edge[0]))

Dijkstra 算法：我的实现有缺陷吗？

Dijkstra's algorithm: is my implementation flawed?

algorithm

graph

dijkstra

python-3.x