【算法】迪克斯特拉算法之Java实现

 迪克斯特拉算法是带权重的最短路径算法。

算法核心思想：

1. 找出当前距离起点距离最短的点。

2. 遍历该点的所有邻居节点，如果经过该点到邻居节点的距离比邻居原来的距离要更短，则更新邻居的距离。

3. 标记该点为已使用节点，寻找下一个未使用的且距离起点最近的节点。重复1,2操作。

4. 所有的节点都被标记后，最短路径就找到了！

举个例子：

public static void DijkstraAlgorithm() {//初始化最短路径拓扑图List<String> points = Arrays.asList("start", "A", "B", "end");int size = points.size();Object[][] graph = new Object[size][size];graph[points.indexOf("start")][points.indexOf("A")] = 6;graph[points.indexOf("start")][points.indexOf("B")] = 2;graph[points.indexOf("A")][points.indexOf("end")] = 1;graph[points.indexOf("B")][points.indexOf("A")] = 3;graph[points.indexOf("B")][points.indexOf("end")] = 5;//当前节点String currentPoint = points.get(0);//记录所有检查过的点List<String> checked = new ArrayList<>();//记录各个点到起点的距离，下标与points对应Integer[] costs = new Integer[size];//起点到起点的距离为0，其他节点距离暂时未知costs[0] = 0;while (true) {int pointIndex = points.indexOf(currentPoint);System.out.println("当前检查点：" + currentPoint);for (int i = 0; i < graph[pointIndex].length; i++) {//当前节点到邻居的距离Object currentCost = graph[pointIndex][i];//过滤空节点和当前节点if (currentCost == null || i == pointIndex) {continue;}//从当前节点出发，到达邻居节点的距离比邻居节点原来的距离更短，则更新邻居节点的总里程。int newCost = costs[pointIndex] + (int) currentCost;if (costs[i] == null || newCost < costs[i]) {costs[i] = newCost;System.out.println("发现点" + points.get(i) + "更短距离：" + newCost);}}//记录已经检查过的点checked.add(currentPoint);//查找还未检查过的，距离起点最短的点currentPoint = getMinCostPoint(points, checked, costs);//如果当前节点为终点，跳出循环if (currentPoint.equals(points.get(points.size() - 1))) {break;}System.out.println("下一个检查点为：" + currentPoint);System.out.println("--------------------------");}System.out.println("--------------------------");System.out.println("当前最短路径为：" + costs[size - 1]);}private static String getMinCostPoint(List<String> points, List<String> checked, Integer[] costs) {String currentPoint;int index = 0;int length = Integer.MAX_VALUE;for (int i = 1; i < costs.length; i++) {//不含已经检查过的点if (checked.contains(points.get(i))) {continue;}if (costs[i] != null && costs[i] < length) {length = costs[i];index = i;}}currentPoint = points.get(index);return currentPoint;}

运行结果：

当前检查点：start
发现点A更短距离：6
发现点B更短距离：2
下一个检查点为：B
--------------------------
当前检查点：B
发现点A更短距离：5
发现点end更短距离：7
下一个检查点为：A
--------------------------
当前检查点：A
发现点end更短距离：6
--------------------------
当前最短路径为：6