使用 PriorityQueue 实现 Dijkstra 算法得到错误结果

Question

我已经使用 Python 中 queue 模块的 PriorityQueue class 实现了 Dijkstra 算法。

但是根据在线判断，我并不总是得到正确的结果。下面给出的代码中一定缺少某些东西，但我不知道是什么。

我的代码有什么问题？

from queue import PriorityQueue

class Solution:
    #Function to find the shortest distance of all the vertices
    #from the source vertex S.
    def dijkstra(self, V, adj, S):
        #code here
        q=PriorityQueue()
        distance=[-1]*V
        distance[S]=0
        visited=set()
        visited.add(S)
        for i in adj[S]:
            distance[i[0]]=distance[S]+i[1]
            q.put([i[1],i[0]])
        while not q.empty():
            w,s=q.get()
            visited.add(s)
            for i in adj[s]:
                d=distance[s]+i[1]
                if distance[i[0]]==-1:
                    distance[i[0]]=d
                elif distance[i[0]]>d:
                    distance[i[0]]=d
                if i[0] not in visited:
                    q.put([i[1],i[0]])
        return distance
            

#{ 
#  Driver Code Starts
#Initial Template for Python 3

import atexit
import io
import sys
    
if __name__ == '__main__':
    test_cases = int(input())
    for cases in range(test_cases):
        V,E = map(int,input().strip().split())
        adj = [[] for i in range(V)]
        for i in range(E):
            u,v,w = map(int,input().strip().split())
            adj[u].append([v,w])
            adj[v].append([u,w])
        S=int(input())
        ob = Solution()
        
        res = ob.dijkstra(V,adj,S)
        for i in res:
            print(i,end=" ")
        print()

# } Driver Code Ends

一个测试用例的示例输入：

预期输出：

0 4 12 19 21 11 9 8 14

问题：

我的代码returns改为：

0 4 12 19 26 16 18 8 14

Answer 1

问题是你优先考虑权重最小的edges，但是你应该优先考虑paths最轻。

你的代码更改即将结束：

q.put([i[1],i[0]])

至：

q.put([d,i[0]])

这将解决问题。

然而，一些评论：

如果您使用优先级队列，则不必将先前存储的节点距离与新距离进行比较，因为优先级队列的作用是确保您首先通过最短路径访问节点访问。通过一些代码重组，您可以摆脱最小距离测试。

一旦你有了它，你也不需要 visited，因为检查节点的距离是否仍然是 -1 就足够了（假设权重从不为负）。出现这种情况，说明你还没有去过。

如果将元组存储在队列而不是列表中，效率也会更高一些。

并且你可以重新组织代码，这样你只需要在开始遍历循环之前将初始单元格推入队列。

最后，如果您使用描述性名称，而不是一个字母变量，则更具可读性，例如 node 和 weight:

class Solution:
    def dijkstra(self, V, adj, S):
        queue = PriorityQueue()
        distances = [-1] * V
        queue.put((0, S))
        while not queue.empty():
            dist, node = queue.get()
            if distances[node] == -1:
                distances[node] = dist
                for neighbor, weight in adj[node]:
                    queue.put((dist + weight, neighbor))
        return distances

使用 PriorityQueue 实现 Dijkstra 算法得到错误结果

Getting wrong results with implementation of Dijkstra's algorithm using PriorityQueue

algorithm

graph

dijkstra

shortest-path

python-3.x

一个测试用例的示例输入：

预期输出：

问题：