简谈迪克斯特拉算法
一、前言
一直想要学点简单的算法，叨叨了好久，开始吧【这篇文章的前言无非就是我想说点废话，大家可以选择性的过滤哈。】
二、概述
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
【简谈迪克斯特拉算法】敲黑板~进入正题
迪杰斯特拉算法是目前OIER们最爱用的最短路算法，下面讲一下这个算法的思路【图丑，请大家忍耐一下】：
文章图片
例图
第一步，我们先把a加入集合，数组变成（s = {a}, dis[] = {0, ∞,∞,∞,∞,∞,∞,∞}）
第二步，找到和a最近的点，为b，把b加入集合，并确定他的最短路径【要注意箭头方向哈】，数组变成（s = {a, b}, dis[] ={0,2,∞,∞,∞,∞,∞,∞}）
第三步，找到和b最近的点，为d，把d加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d}, dis[] = {0,2,∞,3,∞,∞,∞,∞}）
第四步，找到和d最近的点，为e，把e加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e}, dis[] = {0,2,∞,3,5,∞,∞,∞}）
第五步，找到和e最近的点，为f，把f加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f}, dis[] = {0,2,∞,3,5,9,∞,∞}）
第六步，找到和f最近的点，为g，把g加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f, g}, dis[] = {0,2,∞,3,5,9,12,∞}）
第七步，目前只剩下c和h了，那么我们先要找到距离集合路径最短的c，把c加入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g}, dis[]= {0,2,13,3,5,9,12,∞}）
第八步，最后一步，我们找到距离集合路径最短的h，把h加入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g, h}, dis[] = {0,2,13,3,5,9,12,18}）
得嘞，这个大致的思路是这样的，还有后续哟，欲知后事如何，请看下回讲解~
推荐阅读
- 凯迪克金奖绘本《外公的旅程》读懂故乡与远方
- 伦敦市长萨迪克汗Crossrail受挫，转进准备引入租金管控。
- 简谈开源OS发行版
- 简谈区块链与心理预期
- Socket，TCP/UDP和HTTP之间的关系简谈
- 算法|面向过程迪杰斯特拉算法
- java图论弗洛伊德和迪杰斯特拉算法解决最短路径问题
- 电影-简谈霸王别姬
- POJ 2472 迪杰斯特拉计算最长路
- 2021-05-15《仿生人会梦见电子羊吗（》|2021-05-15《仿生人会梦见电子羊吗？》 [美] 菲利普·迪克 著 许东华 译）