algorithm - Dijkstra 算法 : is my implementation flawed?

Question

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

它在很多情况下都能很好地工作，但并非总是如此。

例如，我坚持 this one : 测试用例运行良好，我也尝试了自己的自定义测试用例，但是当我提交以下解决方案时，法官一直告诉我“错误答案”，并且预期结果与我的输出非常不同，确实。

请注意，法官针对相当复杂的图(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]))