一、引言
从前有一个小小的村庄，在村庄里面有许多的村民，这些村民有一个相同的爱好
他们喜欢每天去不同的人家串门，一起喝喝酒、打打牌（呜呜呜，羡慕了）
但最近他们有一个比较烦恼的问题，小A想去小D家，但怎么去才能让路程最短呢？
毕竟，这个村庄每天有无数人来串门，如果能够找到一个路程最短的路线，能为这个村庄提供巨大的帮助
我们的小黄这一天正巧来到这个村庄，利用 最短路 的知识解决了该问题，获得了村民的一致好评
让我们一起看看，最短路 如何解决的该问题
在阅读本文章之前，建议阅读下列文章：
二、什么是最短路
我们把上述的村庄抽象为下列的图：
我们观察一下，从 A 点到 C 点，路线有无数种
- A - E - C：
2 + 4 = 6 - A - D - C：
6 + 1 = 7 - A - B - C：
3 + 10 = 13 - …省略
我们可以看到，从图上来讲，我们选择 A - E - C 这条路线是最短的
我们怎么通过计算机求出来呢
三、迪杰特斯拉算法
我们还是以这张图为基础
我们要求的目标：A 到 C 的最短距离
1、我们从 A 点开始，记录其路程
对于 A 点来说，所能到达的地方如下：
A -> B = 3A -> E = 2A -> D = 6
我们更新表中的值，如下：蓝色代表已经使用完的节点
2、我们从中找出一个路程最短的点：E，分析其能达到的地方
E -> B = 7E -> C = 4
我们更新表的值，如下：
这里可能有些读者可能会有两个疑问
- 第一：路程是怎么样变化的
- 我们本次求的是
A点到其他点的最短路径 C的路程变成6：求A点到C点时，路径为：A - E - C，所以路程为：A-> E+E -> C=2 + 4
- 第二：为什么E点用完就确定是最短的
- 我们在进行选择时，始终选择的是当前所有节点中最小的节点
- 意味着当前我们
A -> E的长度是小于所有A到其他点的距离的
3、我们从中找出一个路程最短的点：B，分析其能达到的地方
B -> C = 7
我们更新表的值：
、我们从中找出一个路程最短的点：D，分析其能达到的地方
D -> E = 12D -> C = 1
我们更新表的值：
5、我们从中找出一个路程最短的点：C，分析其能达到的地方
- 无
我们更新表的值：
最终我们可以看到，我们 A 点到其他点的最短路径
四、迪杰特斯拉算法代码
public HashMap<Node, Integer> dijkstra(Node from) { // 创建一个点 from 到达其他各位置的 map 映射 // key:节点，value:路程 HashMap<Node, Integer> map = new HashMap<>(); // 将 from 自己到达自己的距离设置为 0 map.put(from, 0); // 当前已经确定的点,便于后续进行筛选 HashSet<Node> set = new HashSet<>(); // 找到当前路程最小并且没有被确定的点 Node minNode = getMinDistanceAndUnselectedNode(map, set); while (minNode != null) { // 遍历该点的所有边 for (Edge edge : minNode.edges) { // 看一下是否是已经确定的点 if (!set.contains(edge.to)) { if (map.containsKey(edge.to)) { // 如果该点被访问过 // 比较路程大小，看是否需要更新 if (edge.weight + map.get(minNode) < map.get(edge.to)) { map.put(edge.to, edge.weight + map.get(minNode)); } } else { // 如果该点还没有被访问过 map.put(edge.to, edge.weight + map.get(minNode)); } } } set.add(minNode); minNode = getMinDistanceAndUnselectedNode(map, set); } return map; } public Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> map, HashSet<Node> set) { Node minNode = null; int minValue = Integer.MAX_VALUE; for (Node node : map.keySet()) { if (!set.contains(node)) { if (map.get(node) <= minValue) { minNode = node; minValue = map.get(node); } } } return minNode; }
不仅包括图的源码，还包括如下内容：
五、总结
简单来说，迪杰特斯拉算法在我们日常生活和业务中都有所存在
比如百度地图、高德地图、美团外卖等，怎么确定两点间的最短距离是关键
当然，看完本篇文章之后，也需要大量的场景去进行练习，不然容易生疏
- 743. 网络延迟时间【模板题】
- 当然，我们会发现在每一次寻找
getMinDistanceAndUnselectedNode浪费了大量的时间，基于堆优化的迪杰斯特拉算法对此做了优化，有兴趣的读者可以去看看，这里就不再论述了
