大权值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。