两点间最短间隔 - Dijkstra

一、汇总

算法	场景	说明	参考
BFS	树 无权图的搜刮	标准BFS默认搜刮一条最短路径 改造后可以输出全部最短路径	https://blog.csdn.net/m0_37145844/article/details/144534202
DFS	走迷宫	重要利用回溯算法思想，不包管最短路径	https://blog.csdn.net/m0_37145844/article/details/144534202
Dijkstra 复制代码	带权图最短路径的经典解法	重要利用贪心思想，其中在u打印路径时候包含递归，回溯等思想	本篇解说

二、Dijkstra 原理

借助java工具类：PriorityQueue 默认内部元素逼迫根据指定规则举行自然排序的的小顶堆，每次选择下层节点到起点开始算的最小权值的节点作为当前节点，举行向外的下一个层级的探索，最终让全部节点都保存了，此节点从开始节点的最小权重值及其最短路径的父节点。
三、Dijkstra 代码实现-Java版本

有必要解说一下代码结构：

• 内部类的利用
  
  
  • 表现更强的封装性，结构体仅供外部类利用，不对外袒露。
    
  • 外部类可以直接调用内部类，简化代码。
    
  • 内部类也可以直接利用外部类的成员变量，此例子中暂无表现。
    
  
  
• 优先级队列的利用
  
  
  • 比力器的构造。
    
  • 因为每次向外层探索时候，都会加入下一层到开始节点权重总和最小的节点，此数据结构逼迫举行排序，序列化为一个小顶堆。这也是提升此算法性能的关键设计。
    
  • 默认为小顶堆。
    
  • 间隔Map和路径反向记录Map，都表现了算法设计的技巧。
    
  • 尤其在打印路径时候，最终用递归思想。
    
  
  

1. package algo.backtrace.Dijkstra.weiwei;
3. import java.util.*;
5. public class Dijkstra {
7.     class Grap {
9.         // 带权重的无向图表示，邻接矩阵表示
10.         Map<Integer, List<Edag>> adjList;
12.         Grap() {
13.             adjList = new HashMap<>();
14.         }
16.         // 添加边
17.         public void addEdag(int start, int des, int weight) {
18.             adjList.putIfAbsent(start, new ArrayList<>());
19.             adjList.putIfAbsent(des, new ArrayList<>());
20.             adjList.get(start).add(new Edag(des, weight));
21.             adjList.get(des).add(new Edag(start, weight));
22.         }
24.         // 获取一个顶点的所有边
25.         public List<Edag> getEdags(int node) {
26.             return adjList.getOrDefault(node, new ArrayList<>());
27.         }
29.         // 获取所有顶点
30.         public Set<Integer> getAllNodes() {
31.             return adjList.keySet();
32.         }
33.     }
35.     // 描述边
36.     class Edag{
37.         int des;
38.         int weight;
39.         Edag(int des, int weight) {
40.             this.des = des;
41.             this.weight = weight;
42.         }
43.     }
45.     public Map<Integer, Integer> dijkstra(Grap grap, Integer start) {
46.         // 定义工具
47.         PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[1]));
48.         Map<Integer, Integer> dist = new HashMap<>();
49.         Map<Integer, Integer> prev = new HashMap<>();
51.         // 初始化参数
52.         for (Integer node : grap.getAllNodes()) {
53.             dist.put(node, Integer.MAX_VALUE);
54.             prev.put(node, -1);
55.         }
57.         dist.put(start, 0);
58.         pq.offer(new int[]{start, 0});
60.         while (!pq.isEmpty()) {
61.             int[] poll = pq.poll();
62.             int currNode = poll[0];
63.             int currWeight = poll[1];
65.             if (currWeight > dist.get(currNode)) {
66.                 continue;
67.             }
69.             for (Edag edag : grap.getEdags(currNode)) {
70.                 int newDist = currWeight + edag.weight;
71.                 if (newDist < dist.get(edag.des)) {
72.                     dist.put(edag.des, newDist);
73.                     prev.put(edag.des, currNode);
74.                     pq.offer(new int[]{edag.des, newDist});
75.                 }
76.             }
77.         }
79.         System.out.println("dist:" + dist);
80.         System.out.println("prev:" + prev);
82.         return prev;
83.     }
85.     public void printTrace(Map<Integer, Integer> prevMap, int traget, List<Integer> trace) {
86.         if (prevMap.get(traget) == -1) {
87.             return;
88.         }
90.         traget = prevMap.get(traget);
91.         printTrace(prevMap, traget, trace);
92.         trace.add(traget);
93.     }
95.     public void main(String[] args) {
96.         Grap grap = new Grap();
97.         grap.addEdag(0,1,4);
98.         grap.addEdag(0,2,1);
99.         grap.addEdag(1,3,2);
100.         grap.addEdag(2,3,8);
101.         grap.addEdag(2,4,3);
102.         grap.addEdag(4,5,2);
103.         grap.addEdag(3,5,1);
105.         Dijkstra dijkstra = new Dijkstra();
106.         Map<Integer, Integer> prevMap = dijkstra.dijkstra(grap, 0);
107.         List<Integer> list = new ArrayList<>();
108.         dijkstra.printTrace(prevMap, 5, list);
109.         System.out.println(list);
110.     }
111. }
114. // 输出
115. // dist:{0=0, 1=4, 2=1, 3=6, 4=4, 5=6}
116. // prev:{0=-1, 1=0, 2=0, 3=1, 4=2, 5=4}
117. // [0, 2, 4] 瑕疵之处是traget 没有打印出，无伤大雅。

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。