《算法图解》note 7 狄克斯特拉算法1.狄克斯特拉算法简介2.代码实例

#狄克斯特拉算法

#找出costs中未被标记且值最小的节点
def find_shortest_node(costs,processed):
    shortest_d=float('inf')
    shortest_node=None
    for node, d in costs.items():
        if d<shortest_d and node not in processed:
            shortest_d=d
            shortest_node=node
    return shortest_node
    

#狄克斯特拉算法主体函数
#while循环中，根据当前节点与其邻居节点的距离，尝试到达邻居节点的最短距离
#若找到，更新costs字典中，邻居节点的最短距离，同时将邻居节点的父节点设置为当前节点
def dikjstra(G,costs,parent,processed):
    cur_node=find_shortest_node(costs,processed)
    cur_d=costs[cur_node]
    while cur_node:
        for n,l in G[cur_node].items():
            if l+cur_d<costs[n]:
                costs[n]=l+cur_d
                parent[n]=cur_node
        processed.add(cur_node)
        cur_node=find_shortest_node(costs,processed)


#图
G={
    'A':{'B':3,'C':7},
    'B':{'C':2,'D':4},
    'C':{'D':1,'E':6},
    'D':{'E':3},
    'E':{}
}

#记录从起点到达当前节点的最短距离
costs={
    'A':0,
    'B':float('inf'),
    'C':float('inf'),
    'D':float('inf'),
    'E':float('inf'),
}

#在到达当前节点的距离最短路线下，当前节点的父节点
parent={}

#记录已被处理过的节点
processed=set()

#运行狄克斯特拉算法
dikjstra(G,costs,parent,processed)
#根据运算结果显示最短路径
shortest_path=[]
cur_dot='E'
while cur_dot:
    shortest_path.append(cur_dot)
    cur_dot=parent.get(cur_dot)
shortest_path.reverse()
print(shortest_path)