数据结构学习 | 迪杰斯特拉（附算法实现）

我眼中的迪杰斯特拉算法

网上有很多种解释，我眼中的算法是用在拓扑结构中求解最短路径类问题。这里拓扑结构需要有源结点、目的结点、其它结点、开销值。
核心可以总结为三步

1. 找到不在visited里，而且距离源节点cost最小的点
2. 遍历此点，更新此点邻居的cost
3. 将此点加入visited

实例

比如我们有以下拓扑图，想知道从A 到F的最短路径是什么

算法实现

一些条件初始化

dist={1:{2:1,3:12},2:{4:3,3:9},3:{5:5},4:{5:13,6:15},5:{6:4},6:{6:0}}
cost={1:0,2:1,3:12,4:999,5:999,6:999}
parent={}
for i in range(1,6):
    parent[i]=None
parent[2]=1
parent[3]=1
visited=[1]

def find_shortest_node(cost):
    minD=999
    node=None
    for i in dist.keys():
        if i not in visited:
            if cost[i]<minD:
                
                minD=cost[i]
                node=i
    return node

node=find_shortest_node(cost)
while node:
    for i in dist[node]:
        newcost=cost[node]+dist[node][i]
        if newcost<cost[i]:
            cost[i]=newcost
            parent[i]=node
    visited.append(node)
    node=find_shortest_node(cost) #一定要放在最后

def show_path(des):
    path=[]
    #print(des,"<-",end="")
    path.append(des)
    while parent[des]:
        path.append(parent[des])
        #print(parent[des],"<-",end="")
        des=parent[des]
    return path.reverse()