<p><strong>更新</strong></p>
<p>正如我所评论的,我不认为Dijkstra的算法是最好的方法,但我已经更新了您的代码,使其能够工作。我在修改的行中添加了注释。这些变化有两种类型:</p>
<ol>
<li>用小写字母“updated”注释的行表示仅影响性能的微小更改,例如用集合替换列表的使用,或者改进样式,例如不再需要try-except块</李>
<li>用大写字母“UPDATED”注释的行表示需要纠正的实际问题</李>
<li>我删除了Dijkstra实现,因为它在帮助您发现程序错误方面没有任何用处。但是,考虑一下:你估计当前X到Y位置的距离是一个字典,其字典是一个元组^ {< CD1> },{{< CD2}}是数组[x,y]上数组的内容,其值是距离。为什么不使用一个由x和y索引的二维数组,其值是距离,这就是我所使用的</李>
</ol>
<p>更正后的代码:</p>
<pre><code>import numpy as np
def readfile(filename):
file = open(filename,"r")
ar=np.zeros((80,80), dtype=np.int32) #updated: use an integer type
sp={}
for i in range(80):
l=file.readline()
line=l.split(',')
for j in range(80):
ar[i][j]=int(line[j])
sp[(int(line[j]),i,j)]=10000000
return ar,sp
def extract_min():
min_n,i,j=100000,-1,-1
for n in Q:
if n[0]<min_n:
min_n=n[0]
i=n[1]
j=n[2]
return min_n,i,j
def adj(u): #updated: new replacement that does not use try/except
l = []
row = u[1]
col = u[2]
if row < 79:
l.append((ar[row+1][col], row+1, col))
if col < 79:
l.append((ar[row][col+1], row, col+1))
return l
def relax(u,v):
if sp[v]>sp[u]+v[0]:
sp[v]=sp[u]+v[0]
parent[v]=u
return True # UPDATED
return False #UPDATED
def dijkstra():
Q.add(source) #updated
#S=[] #UPDATED
while len(Q)!=0:
u=extract_min()
Q.remove(u)
#S.add(u) #UPDATED
for v in adj(u):
if relax(u, v) and v not in Q: #UPDATED
Q.add(v) #UPDATED
def print_path_and_sum(): #updated
l = []
n = dest
while n:
l.append(n)
n = parent.get(n)
sum = 0
while l:
n = l.pop()
sum += n[0]
print(n)
print(sum)
ar,sp=readfile("p081_matrix.txt")
source=(ar[0][0],0,0)
dest=(ar[79][79],79,79)
sp[source]=source[0]
Q=set() # updated
parent={}
dijkstra()
print_path_and_sum() #updated
print(sp[dest])
</code></pre>
<p><strong>不同的解决方案</strong></p>
<pre><code>def solve(matrix):
MAX_N = len(matrix) - 1
# do last row:
for col in range(MAX_N - 1, -1, -1):
matrix[MAX_N][col] += matrix[MAX_N][col + 1]
# do remaining rows:
for row in range(MAX_N - 1, -1, -1):
for col in range(MAX_N, -1, -1):
if col == MAX_N:
matrix[row][col] += matrix[row + 1][col]
else:
matrix[row][col] += min(matrix[row][col+1], matrix[row + 1][col])
return matrix[0][0]
matrix = []
with open('p081_matrix.txt') as f:
for line in f:
matrix.append([int(n) for n in line.split(',')])
print(solve(matrix))
</code></pre>
<p><strong>使用路径信息发布不同的解决方案</strong></p>
<pre><code>from copy import deepcopy
def solve(matrix):
for row in range(MAX_N, -1, -1):
for col in range(MAX_N, -1, -1):
if row == MAX_N and col == MAX_N:
continue
if col == MAX_N:
follow[(row, col)] = (row + 1, col)
matrix[row][col] += matrix[row + 1][col]
elif row == MAX_N:
follow[(row, col)] = (row, col + 1)
matrix[row][col] += matrix[row][col + 1]
elif matrix[row][col+1] < matrix[row + 1][col]:
follow[(row, col)] = (row, col + 1)
matrix[row][col] += matrix[row][col + 1]
else:
follow[(row, col)] = (row + 1, col)
matrix[row][col] += matrix[row + 1][col]
return matrix[0][0]
def print_path_and_sum():
sum = 0
t = (0, 0)
while t:
v = matrix_copy[t[0]][t[1]]
print(t, v)
sum += v
t = follow.get(t)
print(sum)
matrix = []
with open('p081_matrix.txtt') as f:
for line in f:
matrix.append([int(n) for n in line.split(',')])
MAX_N = len(matrix) - 1
follow = {}
matrix_copy = deepcopy(matrix)
solution = solve(matrix)
print_path_and_sum()
print(solution)
</code></pre>