时间戳

首页 > 解决方案 > 即使通过了示例测试用例，Dijkstra 算法也不起作用

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

问题描述

所以我遵循了维基百科的 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)

标签： pythonalgorithmgraphdijkstra

解决方案

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

您的算法中缺少的主要成分是优先级队列。您确实 import from Queue，但从不使用它。此外，它缺少节点标记为已访问，您似乎已经实现了一个概念，但您已将其注释掉。

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

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

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

要更正您的代码，请查阅同一 Wikipedia 页面上提供的伪代码，我建议您使用优先队列的变体。

在 Python 中，您可以使用heapq在优先级队列 ( heappush, heappop) 上执行操作。

推荐阅读