Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离 。问题引入：指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径” 。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径 。
文章插图
文章插图
文章插图
文章插图
文章插图
文章插图
文章插图
文章插图
下面我们来模拟一下：
文章插图
文章插图
Dijkstra算法具体步骤为：（1）初始时，S只包含源点，即S＝，v的距离为0 。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或 ）（若u不是v的出边邻接点） 。
（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度） 。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权 。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中 。
文章插图
接下来是代码：已经把几个过程都封装成了基本模块：
文章插图
文章插图
【号称最贪心的算法--Dijkstra算法】
推荐阅读
- 太极拳的好处是什么什么时候练习最合适
- 离月亮最近的国家是哪个 月亮之国是印度樱花之国是
- 玩转世界杯 茶叶提神最佳
- 茶的文献认证
- 快艇最高时速是多少公里 快艇最快速度
- 上海最灵验三大寺庙排名 玉佛禅寺
- 最挨宰的4个4S店保养项目，不仅贵还没用，你做过几个？
- 花的心思 茶最懂
- 进藏路线来了，共4条够经典
- 全世界税收最高国家排行榜 欧洲税收最高的国家