python中Dijkstra算法在实地图上的最短路径

Question

我试图用Dijkstra算法在真实地图上找到两个点之间的最短路径，但是在有限的时间内（120秒）我无法得到结果。如何优化我的代码？我只允许用“枕头”作为外包装。在

在map上有两个红点（33193）（749457），我想画出它们中最短的路径。但即使花费很长时间也不能得出结果。我很好地测试了Dijkstra的算法，不知道它是否还有很多缺陷。Dijkstra的算法是用同样的距离创建的——1。在

Here是完整的代码。在

def walkback(P, x, y):
    L = [y]
    while x != y:
        y = P[y]
        L = [y] + L
    return L

def path(A, x, y):
    M = []
    W = [x]
    P = {}
    while W != []:
       u = W.pop()
       if u == y:
            return walkback(P, x, y)
       M.append(u)
       for v in A[u]:
           if not v in M:
               P[v] = u
               W.append(v)
    return None

这是Dijkstra算法。 我为此做了测试。在

^{pr2}$

对于任何像素，白色和红色（开始、结束）都是可移动的点，并设置为0。其他颜色设置为1。在

for x in range(0, w):
    for y in range(0, h):
        (r, g, b, a) = im.getpixel((x, y))
        if (r, g, b) == (255, 0, 0):
            Red.append((x, y))
            arr[y][x] = 0
        elif (r, g, b) == (255, 255, 255):
            arr[y][x] = 0
        else:
            arr[y][x] = 1

这就为任何可移动的点创建了一个图形。对于['0.1'：['0.2'，'0.3']]，这意味着您可以从（0，1）移动到（0，2）和（0，3）。在

def coord2num(x, y):
    z = str(x) + "." + str(y)
    return z

B = {}
for x in range(0, h):
    for y in range(0, w):
        if arr[x][y] != 0:
            continue
        key = coord2num(x, y)
        B[key] = []
        if x - 1 >= 0 and arr[x - 1][y] == 0:
            value = coord2num(x - 1, y)
            B[key].append(value)
        if x + 1 < h and arr[x + 1][y] == 0:
            value = coord2num(x + 1, y)
            B[key].append(value)
        if y + 1 < w and arr[x][y + 1] == 0:
            value = coord2num(x, y + 1)
            B[key].append(value)
        if y - 1 >= 0 and arr[x][y - 1] == 0:
            value = coord2num(x, y - 1)
            B[key].append(value)

我期望输出最短的路径，但它仍然没有时间。在

Answer 1

你必须使用Dijkstra吗？在这里使用A*方法似乎更好，因为您可以很容易地设计一个好的启发式方法（例如曼哈顿距离）。在

这可能会解决你的时间限制问题。另外，在真实的地图上，你应该明确你的图形是如何定义的（你只考虑交集吗？如果没有，你如何削减空间。在