有人能逐行解释下面的Djikstra算法的时间复杂性(最坏情况和背心情况)吗?我在任何地方都找不到详细的解释,因此任何帮助都将不胜感激
def dijkstra(graph,start,pharmacy):
minimumContainmentZones = {}
predecessor = {}
unseenNodes = deepcopy(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 = pharmacy
while currentNode != start:
try:
path.insert(0,currentNode)
currentNode = predecessor[currentNode]
except:
print('Path not reachable')
break
path.insert(0,start)
if minimumContainmentZones[pharmacy] != infinity:
return(pharmacy,minimumContainmentZones[pharmacy],str(path))
目前没有回答
相关问题 更多 >
编程相关推荐