Dijkstra算法基础

基本原理

Dijkstra算法是根据贪心算法实现的，首先找出当前点到所有能到达的点之间最短的距离，然后松弛一次继续循环。所谓松弛一次，就是在已经访问过的点中遍历一遍，看看有没有更近的，如果有更近的就更新距离。这样每次找最近的可达点+松弛遍历历史节点的操作，一直重复就能找到最短路径。 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
算法步骤
指定起始点s。找到起始点相邻的点开始记录将第二步记录的点作为起始点，如果第二部记录了多个点的话，那么按照与起始点s的距离或者权值，其中权值最小的优先依次作为起始点。直到遍历完图中所有的点。
过程图解

known表示是否已知，dv表示临时距离，这个距离实际上是使用已知定点作为中间顶点从s到v的最短路径长，pv记录一起dv变换的最

Dijkstra算法基础最先出现在Python成神之路。