狄克斯特拉算法（Dijkstra算法），《学点算法吧，Python》

目录

狄克斯特拉算法

迪克斯特拉算法原理

狄克斯特拉算法Python实现代码

1.有权图的Python代码实现

2.最低费用表和父节点表的Python实现

 3.狄克斯特拉算法的Python实现

4.计算结果展示

---

狄克斯特拉算法

狄克斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

---

迪克斯特拉算法原理

Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

原理：根据初始点，挨个的把离初始点最近的点一个一个找到并加入集合，集合中所有的点的距离都是该点到初始点最短路径长度，由于后加入的点是根据集合S中的点为基础拓展的，所以也能找到最短路径。

过程可以参考下图

我们来具体分析一下算法过程：

1.先建立三个表格

第一个表是加权图的表格描述，

第二个表是到每个节点的最短距离，我们姑且称为最低费用表 ，可以看到我们整个算法过程都是围绕这个表格展开的。

第三个表是当前最低费用表数据生成的路径描述，由各节点当前选择的父节点组成。用于算法完成后出发节点S到终点节点F的最短路径的生成。

2.从S点出发，先更新到邻居节点的距离，到达A和B分别是5和0，此时我们只知道S→A和S→B两个路径，所以我们对最低费用表，更新A 为 5和B 为 0。同时更新父节点表中A、B的父节点。

具体如下图。（最低费用表代表我们当前能找到的到达相应节点最短的距离，父节点表代表相应路径中节点的父节点。）

 到目前为止我们能得到怎样的结论呢？整个算法的关键其实就在这里。

此时我们从S点出发，找到了两条路也只有这两条路，A和B。

那我们来思考一下，对这两条路进行推导，看看我们能得出什么结论？

• 首先分析距离最小这条路，S→B。我们来考虑有没有可能存在到达B更短的路径？那是不可能的！因为虽然我们经过A之后还是有可能的路径到达B，但是不论经过怎样的路线，它到达B的距离总是大于S→A的距离5，那也必然大于S-B的距离0。所以我们可以肯定的说从S出发到达B的最短路径就是S-B距离为0。（除非存在距离为负数的路径，但是狄克斯特拉算法是不能处理负权图的，所以不存在这样的路径。如果想要计算负权图那使用Bellman Fork算法解）
• 反之，我们分析并非最小距离的S→A，因为经过B后还可能存在能到达A的路径，这条路径的距离是有可能小于S-A 5的，因为毕竟我们到达B仅仅需要0，只要B后面路径的距离总和小于5就是一条更短的路径。所以到达A的最短距离目前还不能确定，需要进一步确认。
• 按照上面的逻辑推演，不论S点有多少个邻居，找到距离最短的那个邻居，就能确定这个路径是这个邻居节点到S在整张图上是最近路径的。但是也仅仅能确定这一个邻居节点而已，其他的节点的最短路径距离需要后续的计算准建确定。但是计算的原理跟上面是相似的。
• 所以我们确定了在整个加权图范围中从S出发到达B点的最短距离和路径。这是完成计算到F点最短路径的目标迈出的重要的第一步。

3.目前为止我们已经将最低费用表节点B的数值确定了，数值为0。同时也获得了到达A点的一种路径距离5。

现在我们的目标是再找到下一个从S出发能到达的距离最近的节点，此时我们的路径存在两种情况，一种是经过节点A，另一种是经过节点B。

4.首先我们对刚刚确认最近节点B的邻居进行距离更新，目的是看看存不存在这样的路径，它经过节点B而且距离比S到达A还要短。或者可以这样表达，下一个最近的节点要么是A要么是B的邻居，因为B的邻居再向外扩展只能增加距离毕竟这个加权图不允许存在负权边。

此时我们能得到S→A、S→B→C、S→B→D三种路径。

 比较最低费用表中三种路径距离数值，数值最小的就是A，通过前面的分析我们已经直到，除非存在负权边，那么不可能存在通过C节点和D节点后再到达A而距离更短的路径。所以我们得到了第二个最近距离节点A

5.根据之前分析，下一个最近距离肯定在S→B→C、S→B→D或者A的邻居中，所以对A的邻居进行距离更新，此时发现，同样是到达D，从A过去要更近，所以对最低费用表和父节点表中D节点的数据进行更新。

 6.依靠最低费用表，我们再次找出下一个最近距离，并继续对刚刚确认的最近距离节点的邻居数据进行更新，如此往复，直到所有的节点全部更新，也就是最低费用表的所有节点全部找到最近的距离，那算法就完成了。

我们再看一下整个算法的演示：

 算法的整个过程有点像游戏中开战争迷雾，我们只关注眼前的节点，并推算出最近的一个，直到全部找出。是一种典型的贪婪算法。

再次强调。适用于加权非负无环图。关键字是加权和无环。

环形图会导致之前确定为最近距离的节点，作为后续节点的邻居被数据更新，而且是更新为比之前大的数值。也会让程序陷入循环。

---

狄克斯特拉算法Python实现代码

1.有权图的Python代码实现

    graph={}
    graph['S']={}
    graph['A']={}
    graph['B']={}
    graph['C']={}
    graph['D']={}
    graph['F']=None
    graph['S']['A']=5
    graph['S']['B']=0
    graph['A']['C']=15
    graph['A']['D']=20
    graph['B']['C']=20
    graph['B']['D']=35
    graph['C']['F']=20
    graph['D']['F']=10

2.最低费用表和父节点表的Python实现

 

    
    #实现最低费用表
    costs={}
    costs['A']=float('inf')#无穷大
    costs['B']=float('inf')
    costs['C']=float('inf')
    costs['D']=float('inf')
    costs['F']=float('inf')
    
    #实现父节点表
    parents={}
    parents['A']=None
    parents['B']=None
    parents['C']=None
    parents['D']=None
    parents['F']=None    

 3.狄克斯特拉算法的Python实现

def dijkstra(graph,costs,parents,start_node):
    processed=[]#用于记录最低费用表中，已经找到的最近路径的节点名称
    # 更新初始节点的邻居
    for node in graph[start_node].items():  # 遍历初始节点邻居距离
        costs[node[0]] = node[1]  # 更新初始节点最低费用表
        parents[node[0]] = start_node  # 更新初始节点邻居的父节点，就是他自己
    node=find_lowest_node(costs,processed) #找出第一个最近节点
    while node is not None:
        #以目前找出的最近的node为起点，更i性能其邻居在最低费用表中的值
        cost=costs[node] #最便宜节点 距离
        neighbors=graph[node]
        if neighbors is not None:#判断节点必须有邻居
            for neighbor in neighbors.keys():
                new_cost=cost+graph[node][neighbor]#计算经过 最近节点 到达新节点后的距离
                if new_cost 
4.计算结果展示 
加权图：
{'S': {'A': 5, 'B': 0}, 'A': {'C': 15, 'D': 20}, 'B': {'C': 20, 'D': 35}, 'C': {'F': 20}, 'D': {'F': 10}, 'F': None}
最低费用图：
{'A': inf, 'B': inf, 'C': inf, 'D': inf, 'F': inf}
父节点图：
{'A': None, 'B': None, 'C': None, 'D': None, 'F': None}
计算结果：
{'A': 5, 'B': 0, 'C': 20, 'D': 25, 'F': 35} {'A': 'S', 'B': 'S', 'C': 'B', 'D': 'A', 'F': 'D'}
 

写在后面
 
计算路段最少路径使用广度优先搜索
计算加权非负无环图最快路径使用狄克斯特拉算法，Dijkstra's algorithm
计算包含负边的图，要找出最短路径，使用贝尔曼-福德算法，Bellman-Ford algorithm