一、汇总
| 算法 | 场景 | 说明 | 参考 |
| 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，都体现了算法设计的技巧。
- 尤其在打印路径时候，最终用递归思想。
package algo.backtrace.Dijkstra.weiwei;import java.util.*;public class Dijkstra {class Grap {// 带权重的无向图表示，邻接矩阵表示Map<Integer, List<Edag>> adjList;Grap() {adjList = new HashMap<>();}// 添加边public void addEdag(int start, int des, int weight) {adjList.putIfAbsent(start, new ArrayList<>());adjList.putIfAbsent(des, new ArrayList<>());adjList.get(start).add(new Edag(des, weight));adjList.get(des).add(new Edag(start, weight));}// 获取一个顶点的所有边public List<Edag> getEdags(int node) {return adjList.getOrDefault(node, new ArrayList<>());}// 获取所有顶点public Set<Integer> getAllNodes() {return adjList.keySet();}}// 描述边class Edag{int des;int weight;Edag(int des, int weight) {this.des = des;this.weight = weight;}}public Map<Integer, Integer> dijkstra(Grap grap, Integer start) {// 定义工具PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[1]));Map<Integer, Integer> dist = new HashMap<>();Map<Integer, Integer> prev = new HashMap<>();// 初始化参数for (Integer node : grap.getAllNodes()) {dist.put(node, Integer.MAX_VALUE);prev.put(node, -1);}dist.put(start, 0);pq.offer(new int[]{start, 0});while (!pq.isEmpty()) {int[] poll = pq.poll();int currNode = poll[0];int currWeight = poll[1];if (currWeight > dist.get(currNode)) {continue;}for (Edag edag : grap.getEdags(currNode)) {int newDist = currWeight + edag.weight;if (newDist < dist.get(edag.des)) {dist.put(edag.des, newDist);prev.put(edag.des, currNode);pq.offer(new int[]{edag.des, newDist});}}}System.out.println("dist:" + dist);System.out.println("prev:" + prev);return prev;}public void printTrace(Map<Integer, Integer> prevMap, int traget, List<Integer> trace) {if (prevMap.get(traget) == -1) {return;}traget = prevMap.get(traget);printTrace(prevMap, traget, trace);trace.add(traget);}public void main(String[] args) {Grap grap = new Grap();grap.addEdag(0,1,4);grap.addEdag(0,2,1);grap.addEdag(1,3,2);grap.addEdag(2,3,8);grap.addEdag(2,4,3);grap.addEdag(4,5,2);grap.addEdag(3,5,1);Dijkstra dijkstra = new Dijkstra();Map<Integer, Integer> prevMap = dijkstra.dijkstra(grap, 0);List<Integer> list = new ArrayList<>();dijkstra.printTrace(prevMap, 5, list);System.out.println(list);}
}// 输出
// dist:{0=0, 1=4, 2=1, 3=6, 4=4, 5=6}
// prev:{0=-1, 1=0, 2=0, 3=1, 4=2, 5=4}
// [0, 2, 4] 瑕疵之处是traget 没有打印出，无伤大雅。