Python Dijkstra算法內存錯誤？

Question

我已將this answer for Dijkstra Algorithm複製並粘貼到我的項目中。經過幾次簡單的測試後，這似乎很好

在我的具體實現中，我需要算法返回節點列表。所以我必須修改原始代碼，以便它總是返回一個列表。更具體地說，我刪除了所有return "string"線。由我修改後的代碼如下：

## using Dijkstra Algorithm ## 
def choosePath(s, t): 
    net = {'0':{'1':138, '9':150}, 
     '1':{'0':138, '2':178, '8':194}, 
     '2':{'1':178, '3':47.5}, 
     '3':{'2':47.5, '4':70}, 
     '4':{'3':70, '5':70}, 
     '5':{'4':70, '6':36}, 
     '6':{'5':36, '7':50}, 
     '7':{'6':50, '8':81}, 
     '8':{'7':81, '9':138, '1':194}, 
     '9':{'8':138, '0':150}} 
    # sanity check 
    if s == t: 
     return [] 
    # create a labels dictionary 
    labels={} 
    # record whether a label was updated 
    order={} 
    # populate an initial labels dictionary 
    for i in net.keys(): 
     if i == s: labels[i] = 0 # shortest distance form s to s is 0 
     else: labels[i] = float("inf") # initial labels are infinity 
    from copy import copy 
    drop1 = copy(labels) # used for looping 
    ## begin algorithm 
    while len(drop1) > 0: 
     # find the key with the lowest label 
     minNode = min(drop1, key = drop1.get) #minNode is the node with the smallest label 
     # update labels for nodes that are connected to minNode 
     for i in net[minNode]: 
      if labels[i] > (labels[minNode] + net[minNode][i]): 
       labels[i] = labels[minNode] + net[minNode][i] 
       drop1[i] = labels[minNode] + net[minNode][i] 
       order[i] = minNode 
     del drop1[minNode] # once a node has been visited, it's excluded from drop1 
    ## end algorithm 
    # print shortest path 
    temp = copy(t) 
    rpath = [] 
    path = [] 
    while 1: 
     rpath.append(temp) 
     if order.has_key(temp): 
      temp = order[temp] 
     if temp == s: 
      rpath.append(temp) 
      break 
    for j in range(len(rpath)-1,-1,-1): 
     path.append(rpath[j]) 
    return [junctions[int(elem)] for elem in path] 

然後當我運行它，我結束了以下錯誤：顯然

>>> Traceback (most recent call last): 
    File "C:\Users\...\simulation.py", line 162, in choosePath 
    rpath.append(temp) 
MemoryError 

，那是因爲我已經刪除了回報「字符串「行。但是，我沒有找到哪個刪除使它死亡。爲什麼這樣？

我該如何讓它重新工作，並總是返回一個列表而不是字符串，因爲我希望？

Answer 1

我懷疑你的問題是你錯誤的參數傳遞給函數。您想致電choosePath('0', '9')。字符串。不是整數。

有趣的是，如果你刪除的程序的任何部分仍然存在，它會抓住並停止程序。有了這個部分，它捕捉到你的輸入是否錯誤。

if net.has_key(s)==False: 
    return "There is no start node called " + str(s) + "." 
if net.has_key(t)==False: 
    return "There is no terminal node called " + str(t) + "." 

有了這個部分，它捕獲，如果它從未達到的解決方案。

else: return "There is no path from " + str(s) + " to " + str(t) + "." 

完整性檢查不是嚴格必要的，因爲正如你所提到的一個路徑是在你的網絡中保證的。儘管如此，如果你選擇改變周圍的事情，你會知道計算機會給你發出明顯的錯誤。一種選擇是將它們替換爲例外，因爲除非出現可怕的錯誤，否則這些消息都不應該真正出現。這是我在下面的代碼中選擇的。

class NoPathException(Exception): 
    pass 

def choosePath(s, t): 
    net = {'0':{'1':138, '9':150}, 
     '1':{'0':138, '2':178, '8':194}, 
     '2':{'1':178, '3':47.5}, 
     '3':{'2':47.5, '4':70}, 
     '4':{'3':70, '5':70}, 
     '5':{'4':70, '6':36}, 
     '6':{'5':36, '7':50}, 
     '7':{'6':50, '8':81}, 
     '8':{'7':81, '9':138, '1':194}, 
     '9':{'8':138, '0':150}} 
    # sanity check 
    if s == t: 
     return [] 
    if not net.has_key(s): 
     raise ValueError("start node argument not in net") 
    if not net.has_key(t): 
     raise ValueError("end node argument not in net") 
    # create a labels dictionary 
    labels={} 
    # record whether a label was updated 
    order={} 
    # populate an initial labels dictionary 
    for i in net.keys(): 
     if i == s: labels[i] = 0 # shortest distance form s to s is 0 
     else: labels[i] = float("inf") # initial labels are infinity 
    from copy import copy 
    drop1 = copy(labels) # used for looping 
    ## begin algorithm 
    while len(drop1) > 0: 
     # find the key with the lowest label 
     minNode = min(drop1, key = drop1.get) #minNode is the nod2 with the smallest label 
     # update labels for nodes that are connected to minNode 
     for i in net[minNode]: 
      if labels[i] > (labels[minNode] + net[minNode][i]): 
       labels[i] = labels[minNode] + net[minNode][i] 
       drop1[i] = labels[minNode] + net[minNode][i] 
       order[i] = minNode 
     del drop1[minNode] # once a node has been visited, it's excluded from drop1 
    ## end algorithm 
    # print shortest path 
    temp = copy(t) 
    rpath = [] 
    path = [] 
    while 1: 
     rpath.append(temp) 
     if order.has_key(temp): 
      temp = order[temp] 
     else: 
      raise NoPathException("no path to solution") 
     if temp == s: 
      rpath.append(temp) 
      break 
    for j in range(len(rpath)-1,-1,-1): 
     path.append(rpath[j]) 

    return path 

測試

a = choosePath('3', '9') 
print(a) 
['3', '4', '5', '6', '7', '8', '9'] 

這是你要找的輸出？