1 回答

TA貢獻1966條經驗 獲得超4個贊
您的代碼實際上存在幾個問題:
您需要指定您的 Djikstra 算法在哪里停止,在您的代碼中沒有提到什么是結束節點(在您的示例中它應該是 0)
計算成本并
cost = result[len(result) - 1]
不能獲得字典中的最后一個元素(字典通常沒有排序,因此“最后一個元素”甚至不存在!)。您應該將成本檢索為cost = result[end]
,其中end
是最終節點,在您的示例中為 0。您將該函數調用為
result = graph.dijkstra(1, 0, graph.vertexs[2].connections, {}, {node: None for node in graphList})
,但是,該函數的第三個參數應該是初始節點的鄰居集,所以它應該graph.vertexs[1].connections
在您的情況下。
綜上所述,為了使代碼按預期工作,可以對函數進行如下修改:
def dijkstra(self, current, currentDistance, distances, visited, unvisited, end):
for neighbour, distance in distances.items():
if neighbour.name not in unvisited:
continue
newDistance = currentDistance + distance
if unvisited[neighbour.name] is None or unvisited[neighbour.name] > newDistance:
unvisited[neighbour.name] = newDistance
visited[current] = currentDistance
if current == end:
return visited
del unvisited[current]
if not unvisited:
return True
candidates = [node for node in unvisited.items() if node[1]]
current, currentDistance = sorted(candidates)[0]
self.dijkstra(current, currentDistance, graph.vertexs[current].connections, visited, unvisited, end)
return visited
并按如下方式調用它:
print("Shortest possible path from node 1 to 0:")
start = 1
end = 0
result = graph.dijkstra(start, 0, graph.vertexs[start].connections, {}, {node: None for node in graphList}, end)
cost = result[end]
path = " ".join([str(arrInt) for arrInt in list(result.keys())])
print(path, "costing", cost)
通過這樣做,輸出變為
從節點 1 到 0 的最短路徑: 1 6 2 0 成本 15
添加回答
舉報