即使通过了示例测试用例，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 导入，但从未使用过它。此外，它缺少已访问节点的标记，您似乎已经实现了一些概念，但您将其注释掉了。

Wikipedia上的算法大纲解释了在每次迭代的最后一步使用这个优先级队列：

Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

目前您的代码中没有选择具有最小距离的已访问节点的机制。相反，它会根据输入中的顺序选择下一个节点。

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

在 Python 中，您可以使用 heapq 对优先级队列执行操作（heappush、heappop）。

即使通过了示例测试用例，Dijkstra 算法也无法正常工作

Dijkstra algorithm not working even though passes the sample test cases

python

algorithm

graph

dijkstra