最短路径算法（Dijkstra）
Dijkstra（ 迪科斯特拉 ）算法是用来解决单源最短路径的算法，要求路径权值非负数。该算法利用了深度优先搜索和贪心的算法。
算法的图解
【最短路径算法（Dijkstra）】下面是一个有权图，求从A到各个节点的最短路径。
文章图片
第1步：从A点出发，判断每个点到A点的路径（如果该点不能直连A点则距离值为无穷大，如果该点能和A直连则是当前的权值），计算完之后把A点上色，结果如下图:
文章图片
第2步：从除A点之外的点查找到距离A点最近的点C，从C点出发查找其邻近的节点（除去已上色的点），并重新计算C点的邻近点距离A点的值，如图中B点，若新值（C点到A点的值+C点到该点的路径）小于原值，则将值更新为5，同理更新D、E点。同时将C标记为已经处理过，如图所示涂色。
文章图片
第3步：从上色的节点中查找距离A最近的B点，重复第3步操作。
文章图片
第4步： 重复第3步，2步，直到所有的节点都上色。
文章图片
最后就算出了从A点到所有点的最短距离。
题目练习
leetcode 743题
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）