概述
适用范围：没有权值为负数的边。
规定一个出发点，这个出发点到所有节点的距离，对于不可达的点可以认为距离无穷大。
假如去往地点的路径和长度已知，那么可以使用dijkstra算法计算某个地点到其他所有地点的最短距离。
单源什么意思？
- 从一个顶点出发，Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。
和bfs求的最短路径有什么区别？
bfs求的与其说是路径，不如说是次数。因为bfs他是按照队列一次一次进行加入相邻的点，而两点之间没有权值或者权值相等(代价相同)。处理的更多是偏向迷宫类的这种都是只能走邻居(不排除特例)。
Dijkstra在处理具体实例的应用还是很多的，因为具体的问题其实带权更多一些。
图解思路
举个例子：下面的无向图描述了A、B、C、D、E五点之间的相互距离。
网络异常，图片无法展示
|
第一步：初始化表格
首先先初始化一个表格，规定A为出发点，那么A到A的距离初始值为0，A到B、C、D、E四点之间的距离均为无穷大。
| A | B | C | D | E | |
| A | 0 | 无穷大 | 无穷大 | 无穷大 | 无穷大 |
第二步：从A出发，看能否让表格中的距离变短
从A出发，已知A到原点（原点也是A）的基础距离是0，是跟A相连的有三个点D、C、B。
- A(0)-B这个路发现了比无穷大更短的距离0+3，因此更新表格第三列值
- A(0)-C这个路发现了比无穷大更短的距离0+15，因此更新表格第四列值
- A(0)-D这个路发现了比无穷大更短的距离0+9，因此更新表格第五列值
- 跟A相连的有三个点D、C、B已经分析完毕，那么A这点就锁死，之后不会再更新值了
| A | B | C | D | E | |
| A | 0（锁死） | 无穷大 -> 3 |
无穷大 -> 15 |
无穷大 -> 9 |
无穷大 |
第三步：从B出发，看能否让表格中的距离变短
从B出发，已知B到原点（原点是A）的基础距离是3，是跟B相连的有三个点A、C、E。
- B(3)-A这个路的距离是3+3，并没有比表格中的数据小，因此不选不更新值
- B(3)-C这个路的距离是3+2，比表格中的数值（15）小，因此更新表格值为5
- B(3)-E这个路的距离是3+200，比表格中的数值（无穷大）小，因此更新表格值为203
- 跟B相连的有三个点A、C、E已经分析完毕，那么B这点就锁死，之后不会再更新值了
| A | B | C | D | E | |
| A | 0 -> 0（锁死） |
3（锁死） | 15 -> 5 |
9 | 无穷大 -> 203 |
第四步：从C出发，看能否让表格中的距离变短
从C出发，已知C到原点（原点是A）的基础距离是5，是跟C相连的有五个点A、B、C、D、E。
- C(5)-A这个路的距离是5+15，并没有比表格中的数据（0）小，因此不选不更新值
- C(5)-B这个路的距离是5+2，并没有比表格中的数据（2）小，因此不选不更新值
- C(5)-C这个路的距离是5+0，不更新值
- C(5)-D这个路的距离是5+7，并没有比表格中的数据（9）小，因此不选不更新值
- C(5)-E这个路的距离是5+14，比表格中的数值（203）小，因此更新表格值为19
- 跟C相连的五个点A、B、C、D、E已经分析完毕，那么C这点就锁死，之后不会再更新值了
| A | B | C | D | E | |
| A | 0 -> 0（锁死） |
3 -> 3（锁死） |
5 -> 5 (锁死) |
9 -> 9 |
203 -> 19 |
第五步：从D出发，看能否让表格中的距离变短
从D出发，已知D到原点（原点是A）的基础距离是9，是跟D相连的有三个点A、C、E。
- D(9)-A这个路的距离是9+9，并没有比表格中的数据（0）小，因此不选不更新值
- D(9)-C这个路的距离是9+7，并没有比表格中的数据（5）小，因此不选不更新值
- D(9)-E这个路的距离是9+16，并没有比表格中的数据（19）小，因此不选不更新值
- 跟D相连的有三个点A、C、E已经分析完毕，那么D这点就锁死，之后不会再更新值了
| A | B | C | D | E | |
| A | 0 -> 0（锁死） |
3 | 5 -> 5 (锁死) |
9（锁死） | 19 -> 19 |
第六步：从E出发，看能否让表格中的距离变短
从E出发，已知E到原点（原点是A）的基础距离是19，是跟E相连的有三个点B、C、D。
- E(19)-B这个路的距离是19+200，并没有比表格中的数据（3）小，因此不选不更新值
- E(19)-C这个路的距离是19+14，并没有比表格中的数据（5）小，因此不选不更新值
- E(19)-D这个路的距离是19+16，并没有比表格中的数据（9）小，因此不选不更新值
- 跟E相连的有三个点B、C、D已经分析完毕，那么E这点就锁死，之后不会再更新值了
此时所有点都已经遍历完毕，因此从A点出发到各点的最短距离就如下表格所示：
| A | B | C | D | E | |
| A | 0 | 3 | 5 | 9 | 19 |
为何Dijkstra算法的适用范围：没有权值为负数的边？
如果有负数的话，那么在比较过程中，已经被锁死的节点会在后续的比较中出现更新的情况。 准确说来，其实是可以出现权值为负数的边，但是不要出现一个整体累加和为负数的环。
因为如果有负数的话，每次去走那条权值为负数的边，累加和都会更小，这样明显是不行的。
代码实现
public class Dijkstra{ public class HashMap<Node, Integer> dijkstra(Node head){ // 从head出发到所有点的最小距离 // key：从head出发到达key // value：从head出发到达key的最小距离 // 如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷 HashMap<Node, Integer> distanceMap = new HashMap<>(); distanceMap.put(head, 0); // 已经求过距离的节点，存在selectedNodes中，以后再也不碰 HashSet<Node> seletcedNodes = new HashSet<>(); Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); while(minNode != null){ int distance = distanceMap.get(minNode); for(Edge edge: minNode.edges){ Node toNode = edge.to; if(!distanceMap.containsKey(toNode)){ distanceMap.put(toNode, distance + edge.weight); } distanceMap.put(edge.to, Math.min(distanceMap.get(toNode),distance + edge.weight)); } selectedNodes.add(minNodes); minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); } return distanceMap; } public static Node getMinDistanceAndUnselectedNode( HashMap<Node, Integer> distanceMap,HashSet<Node> touchedNodes){ Node minNode = null; int minDistance = Integer.MAX_VALUE: for(Entry<Node, Integer> entry: distanceMap.entrySet()){ Node node = entry.getKey(); int distance = entry.getValue(); if(!touchedNodes.contains(node)&&distance<minDistance){ minNode = node; minDistance = distance; } } return minNode; } } }
