本文主要是介绍Dijkstra算法总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.如何建立图
Graph 一般是adjecent list，
class DirectedGraphNode {
int label;
List<DirectedGraphNode> neighbors;
...
}
也可以使用 HashMap 和 HashSet 搭配的方式来存储邻接表
hashmap<Integer, List<Integer>>() 或者HashMap<Integer, HashSet<Integer>>() 来表示；
有时候根据题目需要，图的表示也有HashMap<String, PriorityQueue<String>>()
Dijkstra 算法：
Time Complexity: O(VLogV + ElogV).
Dijkstra写法统一格式，pq加入的时候，不需要加visited，所有的visited在while循环刚poll出来判断，一定不要在下一层pq offer的时候判断，因为这样会漏掉最优解；让pq加进去后，排序后，poll出来的就是最优解；这样是通用的写法，不容易出错！
Maze II 核心思想就是，到达同一个点的时候，step可能不一样，那么我们必须要有一个数据结构去sort一下，每次取最小的step，然后继续往下走，那么这里就是需要PQ，这题考的是Dijkstra (dai ka stra) Algorithm，步骤跟BFS有点不一样的地方是，收集下一层的时候，不能visite = false 就直接赋值visite = true, 那样会漏掉到同样一个点的最小距离；(update its priority if it was already in the pq);
class Solution {private class Node {public int x;public int y;public int step;public Node (int x, int y, int step) {this.x = x;this.y = y;this.step = step;}}public int shortestDistance(int[][] maze, int[] start, int[] destination) {if(maze == null || maze.length == 0 || maze[0].length == 0) {return -1;}int m = maze.length;int n = maze[0].length;boolean[][] visited = new boolean[m][n];PriorityQueue<Node> pq = new PriorityQueue<Node>((a, b) -> (a.step - b.step));pq.offer(new Node(start[0], start[1], 0));int[][] dirs = {{0,1}, {0,-1}, {-1,0}, {1,0}};while(!pq.isEmpty()) {Node node = pq.poll();if(node.x == destination[0] && node.y == destination[1]) {return node.step;}if(visited[node.x][node.y]) {continue;}visited[node.x][node.y] = true;for(int[] dir: dirs) {int nx = node.x;int ny = node.y;int step = node.step;while(isvalid(nx + dir[0], ny + dir[1], maze)) {nx += dir[0];ny += dir[1];step++;}if(!visited[nx][ny]) {pq.offer(new Node(nx, ny, step));}}}return -1;}private boolean isvalid(int x, int y, int[][] maze) {int m = maze.length;int n = maze[0].length;return (0 <= x && x < m && 0 <= y && y < n && maze[x][y] != 1);}
}Cheapest Flights Within K Stops 核心思想就是，每次走最小的cost的路径，那么到达des的时候，就是最小的cost，那么我们需要做的是把边cost的信息，融入到node里面去，那么node进行排序，也就是cost进行排序；graph怎么建立，graph: HashMap<Integer, HashMap<Integer, Integer>> 存 from , <neighbor, cost>将边的信息(cost信息)，整合到node里面去，也就是到达这个city需要的cost是多少，然后剩下的步骤是多少，cost是累加的，剩下的步骤是减少的。pq: 存Node Node<cost, city, step> sort by cost; 搜索：if( step >
这篇关于Dijkstra算法总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
