这是《算法图解》的第7篇读书笔记。其主要内容是简述狄克斯特拉算法。

1.狄克斯特拉算法简介

迪克斯特拉（dijkstra)） 算法用于找出有向无环图（DAG）中两点的最短路径。
对于无权重的有向无环图，狄克斯特拉算法的用途等效于广度优先搜索（BFS）。
对于有权重的图：
若边的权重是相等的正数，其用途等效于广度优先搜索。
若边的权重不等且仅权重均为正数，狄克斯特拉算法能出两点间的最短路径。
若边的权重有负数，则狄克斯特拉算法是不适用的。

2.代码实例

现在将通过python代码找出以下DAG中从A点至E点的最短路径。

DAG.jpg

代码如下：

#狄克斯特拉算法

#找出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)