时间复杂度Djikstra算法的最坏情况和最佳情况?

2024-04-28 14:38:31 发布

您现在位置:Python中文网/ 问答频道 /正文

有人能逐行解释下面的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))

Tags: pathinnodeforifstartgraphpharmacy