算法系列——迪杰斯特拉算法（Dijkstra）

本系列旨在用简单的人话讲解算法尽可能避免晦涩的定义读者可以短时间内理解算法原理及应用细节。我在努力本篇文章编程语言为Python供参考。迪杰斯特拉算法Dijkstra典型最短路径算法。用于计算一个节点到其他节点的最短路径。基本原理从起始点出发重复寻找当前距离起始点最近的且未访问过的结点然后利用该结点更新距离数组直到访问过全部结点为止最终的距离数组即为起始点到其余各点的最短路径距离。1. 邻接矩阵构建基本用途用一个二维数组存放两两结点之间的距离或权值。2. 算法实现最终得到的距离数组的每一项就是起始点到该点的最短距离。3. 最短路径的寻找理论依据由于 距离数组 是不断更新的所以最终 目标点索引 所对应的值一定是 起始点到目标点的最短路径距离。所以最后一次更新这个值的结点一定是最短路径上 目标点的上一个结点。否则就会被更短的再次更新就不可能是最后一次更新由于上一个结点一定是最短路径上的结点所以根据最优化原理principle of optimality上一个结点索引 所对应的值一定是 起始点到该点的最短距离否则就会出现更优路径这条路径就不可能是最短路径。所以以此类推反向推回去一直到起始点就得到了最短路径。有了理论依据再返回去看刚才的距离数组更新过程就可以找出最短路径。配套视频讲解链接【Python算法系列】迪杰斯特拉算法_哔哩哔哩_bilibili附全部源码#北京 天津 郑州 济南 长沙 海南 # 0 1 2 3 4 5 #模拟从文件中读入图的各个路径 a 0 1 500 0 2 100 1 2 900 1 3 300 2 3 400 2 4 500 3 4 1300 3 5 1400 4 5 1500 INF float(inf) #定义邻接矩阵 记录各城市之间的距离 weight [[INF if j!i else 0 for j in range(6)] for i in range(6)] #解析数据 b [[int(i) for i in i.split( )] for i in a.split(\n) if i ! ] for i in b: weight[i[0]][i[1]] i[2] weight[i[1]][i[0]] i[2] def dijkstra(src, target): src : 起点索引 dist: 终点索引 ret: 最短路径的长度 #未到的点 u [i for i in range(6)] #距离列表 dist weight[src][:] #把起点去掉 u.remove(src) #用于记录最后更新结点 last_update [src if i ! INF else -1 for i in dist] while u ! []: idx 0 min_dist INF #找最近的点 for i in range(6): if i in u and dist[i] min_dist: min_dist dist[i] idx i #从未到列表中去掉这个点 u.remove(idx) #更新dist借助这个点连接的路径更新dist for j in range(6): if j in u and weight[idx][j] min_dist dist[j]: dist[j] weight[idx][j] min_dist #记录更新该结点的结点编号 last_update[j] idx #输出从起点到终点的路径结点 tmp target path [] while tmp ! src: path.append(tmp) tmp last_update[tmp] path.append(src) print(-.join([str(i) for i in reversed(path)])) return dist[target]