我已经为 Dijkstra 算法复制并粘贴了这个答案复制并粘贴到我的项目中。经过几次简单的测试后似乎还可以。
在我的具体实现中,我需要算法返回一个节点列表。所以我必须修改原始代码,使其始终返回一个列表。更具体地说,我删除了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
显然,这是因为我删除了返回“字符串”行。但是,我没有找出哪个删除使它死亡。为什么会这样?
我怎样才能让它再次工作并且总是返回一个列表而不是我希望的字符串?