python - 具有大权重的 Dijkstra 算法

Question

我正在尝试解决在线法官关于计算完整图上所有最短路径的问题。可以看到完整的问题规范 here.但是，我超出了所需的内存限制。这是执行 Dijkstra 算法的代码部分:

n = int(raw_input())
dict1 = [[""for i in xrange(n+1)]for j in xrange(n+1)]
edges = [0]
for i in xrange(n):
    x,y = map(int, raw_input().split())
    edges.append((x,y))

for i,coord1 in enumerate(edges):
    for j,coord2 in enumerate(edges):
        if i==j or i==0 or j==0:
            continue

        x1,y1 = coord1
        x2,y2 = coord2
        weight = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
        dict1[i][j] = weight
        dict1[j][i] = weight

x = int(raw_input())
times = []
vertices = {i:1e13 if i!= x else 0 for i in xrange(1,n+1)}
while len(vertices)>0:
    minimum = min(vertices.items(), key=lambda x: x[1])[0]
    currentCost = vertices[minimum]
    times.append(currentCost)
    del vertices[minimum]

    for neighbour,newWeight in enumerate(dict1[minimum]):
        if neighbour in vertices and newWeight != "":
            if currentCost + newWeight < vertices[neighbour]:
                vertices[neighbour] = currentCost + newWeight

由于时间复杂度更好，代码使用了没有优先级队列的原始算法。尽管这给出了正确的答案，但我觉得内存超出与我存储权重的方式有关，考虑到它们可以大到 10^12。是否有另一种方法可以存储使用较少内存的权重，或者是其他原因导致了问题？

Answer 1

您的问题与大权重无关(10^12 不是一个大数字)。如果你想看到这种情况(尝试将它们除以某个数字，如 1000 以查看它也会失败)。

问题是你没有使用优先级队列，这将时间复杂度降低到O(V^2)，如果你使用优先级队列，你会得到O( E + V log(V)).

因此，实现一个普通的 Dijkstra 并将让您的答案被接受。

---

抱歉，还没有读到这是一个平面图并且它是稠密的。知道您的图形由 2d 点组成，您可以利用距离启发式并使用 A* algorithm .