本文主要是介绍【算法】迪克斯特拉算法之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
这篇关于【算法】迪克斯特拉算法之Java实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!