即使通过了示例测试用例，Dijkstra 算法也不起作用

Question

所以我遵循了维基百科关于 Dijkstra 算法和 Brilliants 的伪代码。 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode https://brilliant.org/wiki/dijkstras-short-path-finder/。这是我的代码，它不起作用。谁能指出我代码中的缺陷吗？

# Uses python3

from queue import Queue

n, m = map(int, input().split())
adj = [[] for i in range(n)]

for i in range(m):
    u, v, w = map(int, input().split())
    adj[u-1].append([v, w])
    adj[v-1].append([u, w])

x, y = map(int, input().split())
x, y = x-1, y-1
q = [i for i in range(n, 0, -1)]
#visited = set()
# visited.add(x+1)
dist = [float('inf') for i in range(len(adj))]
dist[x] = 0
# print(adj[visiting])
while len(q) != 0:

    visiting = q.pop()-1
    for i in adj[visiting]:
        u, v = i
        dist[u-1] = dist[visiting]+v if dist[visiting] + \
            v < dist[u-1] else dist[u-1]
# print(dist)
if dist[y] != float('inf'):
    print(dist[y])
else:
    print(-1)

Answer 1

您的算法没有正确实现 Dijkstra 算法。您只需按照输入顺序迭代所有节点，并根据节点的当前距离更新到邻居的距离。但后一个距离并不能保证是最短距离，因为您在某些节点“转弯”之前对其进行迭代。 Dijkstra 算法指定了处理节点的特定顺序，这不一定是输入顺序。

您的算法中缺少的主要成分是优先级队列。您确实从

Queue

导入，但从未使用过它。此外，它缺少已访问节点的标记，您似乎已经实现了这一概念，但您已将其注释掉。

维基百科上的算法概要解释了在每次迭代的最后一步中如何使用此优先级队列：

否则，选择暂定距离最小的未访问过的节点，将其设置为新的“当前节点”，并返回步骤3。

当前代码中没有机制可以选择具有

最小距离的访问节点。相反，它根据输入中的顺序选择下一个节点。

要更正您的代码，请查阅同一维基百科页面上提供的伪代码，我建议使用变体

带有优先级队列。

在 Python 中，您可以使用

heapq

 对优先级队列执行操作（

heappush

、

heappop

）。

Answer 2

问得好。您必须使用优先级队列来跟踪访问的节点，并根据节点/路径的长度对这些节点/路径进行排序（最短的优先）。