Dijkstra算法狄克斯特拉算法，《学点算法吧，Python》 _节点

目录
狄克斯特拉算法
迪克斯特拉算法原理
狄克斯特拉算法实现代码
1.有权图的代码实现
2.最低费用表和父节点表的实现
3.狄克斯特拉算法的实现
4.计算结果展示
狄克斯特拉算法
狄克斯特拉算法()是由荷兰计算机科学家狄克斯特拉于1959年提出的。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
迪克斯特拉算法原理
算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
原理：根据初始点，挨个的把离初始点最近的点一个一个找到并加入集合，集合中所有的点的距离都是该点到初始点最短路径长度，由于后加入的点是根据集合S中的点为基础拓展的，所以也能找到最短路径。
过程可以参考下图
我们来具体分析一下算法过程：
1.先建立三个表格

文章插图
第一个表是加权图的表格描述，
第二个表是到每个节点的最短距离，我们姑且称为最低费用表，可以看到我们整个算法过程都是围绕这个表格展开的。
第三个表是当前最低费用表数据生成的路径描述，由各节点当前选择的父节点组成。用于算法完成后出发节点S到终点节点F的最短路径的生成。
2.从S点出发，先更新到邻居节点的距离，到达A和B分别是5和0 ，此时我们只知道S→A和S→B两个路径，所以我们对最低费用表，更新A为 5和B为 0 。同时更新父节点表中A、B的父节点。
具体如下图。（最低费用表代表我们当前能找到的到达相应节点最短的距离，父节点表代表相应路径中节点的父节点。）
到目前为止我们能得到怎样的结论呢？整个算法的关键其实就在这里。
此时我们从S点出发，找到了两条路也只有这两条路， A和B 。
那我们来思考一下，对这两条路进行推导，看看我们能得出什么结论？
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节点的数据进行更新。

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

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