我使用了一个已经可用的代码，它返回源和目的地之间的最短距离，尝试更新代码以获得源和两个目的地之间的最短路径，基于此我可以比较两条路径。但这似乎不起作用。如果能提供任何帮助，我将不胜感激。
代码如下:
def dijkstra(graph,start,goal):
minimumContainmentZones = {}
predecessor = {}
unseenNodes = graph
infinity = 9999999
path = []
for node in unseenNodes:
minimumContainmentZones[node] = infinity
minimumContainmentZones[start] = 0
while unseenNodes:
minNode = None
for node in unseenNodes:
if minNode is None:
minNode = node
elif minimumContainmentZones[node] < minimumContainmentZones[minNode]:
minNode = node
for childNode, weight in graph[minNode].items():
if weight + minimumContainmentZones[minNode] < minimumContainmentZones[childNode]:
minimumContainmentZones[childNode] = weight + minimumContainmentZones[minNode]
predecessor[childNode] = minNode
unseenNodes.pop(minNode)
currentNode = goal
while currentNode != start:
try:
path.insert(0,currentNode)
currentNode = predecessor[currentNode]
except KeyError:
print('Path not reachable')
break
path.insert(0,start)
if minimumContainmentZones[goal] != infinity:
return(goal,minimumContainmentZones[goal],str(path))
if __name__=="__main__":
graph = {'a':{'b':5,'c':3,'d':2},'b':{'a':3,'e':11,'f':12},'c':{'a':5,'f':7},'d':{'a':2,'f':8,'g':5},'e':{'b':11,'f':3,'h':3},'f':{'b':12,'c':7,'d':8,'e':3,'g':4,'h':7,'i':5,'k':4},'g':{'d':5,'f':4,'k':5},'h':{'e':3,'f':7,'j':2},'i':{'f':5,'j':3} , 'j':{'h':2,'i':3,'k':6} ,'k':{'g':5,'f':4,'j':6} }
a,b,c=dijkstra(graph, 'a', 'h')
d,e,f=dijkstra(graph, 'a', 'j')
print(a,b,c)
print(d,e,f)
给出错误:
Path not reachable
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
<ipython-input-93-bc57edb9feb6> in <module>
40 graph = {'a':{'b':5,'c':3,'d':2},'b':{'a':3,'e':11,'f':12},'c':{'a':5,'f':7},'d':{'a':2,'f':8,'g':5},'e':{'b':11,'f':3,'h':3},'f':{'b':12,'c':7,'d':8,'e':3,'g':4,'h':7,'i':5,'k':4},'g':{'d':5,'f':4,'k':5},'h':{'e':3,'f':7,'j':2},'i':{'f':5,'j':3} , 'j':{'h':2,'i':3,'k':6} ,'k':{'g':5,'f':4,'j':6} }
41 a,b,c=dijkstra(graph, 'a', 'h')
---> 42 d,e,f=dijkstra(graph, 'a', 'j')
43 print(a,b,c)
44 print(d,e,f)
<ipython-input-93-bc57edb9feb6> in dijkstra(graph, start, goal)
32 break
33 path.insert(0,start)
---> 34 if minimumContainmentZones[goal] != infinity:
35 return(goal,minimumContainmentZones[goal],str(path))
36
KeyError: 'j'
问题是第一次调用该函数时，通过删除节点来修改图。然后，第二次调用它时，预期的节点不再存在了!危险来自于使用unseenNodes.pop()。
unseenNodes = graph
创建对同一图的另一个引用，而不是该图的副本。
这里有一个方法来修复它:实际上做一个副本。
在脚本的顶部，使用这一行:
from copy import deepcopy
现在，你说的unseenNodes = graph，把它改成:
unseenNodes = deepcopy(graph)