迪銳克斯拉算法
簡單來說就是在有向圖中，給定一個圖中具體的出發點，從這個點出發能夠到達的所有的點，每個點的最短距離是多少。到不了的點，距離則是正無窮。有向，無負權重，可以有環。
所以說，迪銳克斯拉算法是生成一個從源點出發到各個點的最小距離表。
舉例：有向圖如圖所示
從給定的出發點a出發，最終要獲得的是a到b,c,d,e每個點之間的最短距離。默認a到自己的距離是0，其他的點還沒到達的點的距離是正無窮。已經確定的答案不動，在沒有確定的記錄中找一個最小的出來。
| a | b | c | d | e |
|---|---|---|---|---|
| 0 | 正無窮 | 正無窮 | 正無窮 | 正無窮 |
所以先從a點出發的三條邊1，2，6。中找出權重為1的邊，ad距離為1，小于之前的正無窮（比之前距離小），所以更新a到d之間的距離，bcd同理。所以更新完后距離如下：
| a | b | c | d | e |
|---|---|---|---|---|
| 0 | 2 | 6 | 1 | 正無窮 |
此時，從a出發的三條邊已經走完，所以a點確定下來，再也不動。
其余沒有確定的記錄中d是最短的（從a出發到b的距離為1），所以從d開始向下找（d屬于中間的跳點）。
d出發的邊有兩條，分別是dc和de。其中dc距離為2，再加上之前a到d的距離為1，所以此時a到c的距離經過d跳轉后為3，小于之前的6，所以更新ac之間距離，同樣de距離7小于正無窮。所以也進行更新。d也確定了。
| a | b | c | d | e |
|---|---|---|---|---|
| 0 | 2 | 3 | 1 | 7 |
接下來從不確定的記錄中根據最小的向下找。b點出發的邊有一條be，be距離9加上a到b的距離2，所以be距離為11，大于之前的，不更新。b也確定了。
| a | b | c | d | e |
|---|---|---|---|---|
| 0 | 2 | 3 | 1 | 7 |
還剩下c，從c點出發的邊有兩條，cb和ce，因為b點已經確定了不再動，所以一看ce一條，ce距離為3，a到c距離為3，所以ae之間距離為6，小于之前，更新e點距離。
| a | b | c | d | e |
|---|---|---|---|---|
| 0 | 2 | 3 | 1 | 6 |
代碼
根據上面的分析進行代碼的實現，不過getMinDistanceAndUnSelectNode有瑕疵，因為每找一個minNode就會在集合中都遍歷一次。會在下面進行代碼優化。
public static HashMap<Node, Integer> dijkstra1(Node from) {HashMap<Node, Integer> distanceMap = new HashMap<>();distanceMap.put(from, 0);//已經確定的邊；HashSet<Node> selectedNodes = new HashSet<>();//根據已經確定的記錄 和 map，找出沒確定的中最小的記錄Node minNode = getMinDistanceAndUnSelectNode(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);} else {//edge.weight + distance 當前邊的權重 + 我此時當做跳點的距離。//distanceMap.get(toNode) 已經存在的距離distanceMap.put(toNode, Math.min(distanceMap.get(toNode), (edge.weight + distance)));}}//所有的邊都已經遍歷完，這個點可以確定了，放到確定的集合中。selectedNodes.add(minNode);//再次獲取最小的記錄minNode = getMinDistanceAndUnSelectNode(distanceMap, selectedNodes);}return distanceMap;}public static Node getMinDistanceAndUnSelectNode(HashMap<Node, Integer> distanceMap, HashSet<Node> selectedNode) {Node minNode = null;int minDistance = Integer.MAX_VALUE;for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {Node node = entry.getKey();int distance = entry.getValue();if (!selectedNode.contains(node) && distance < minDistance) {minDistance = distance;minNode = node;}}return minNode;}
)
