力扣labuladong——一刷day84

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

Dijkstra 算法（一般音译成迪杰斯特拉算法）无非就是一个 BFS 算法的加强版，它们都是从二叉树的层序遍历衍生出来的

一、力扣743. 网络延迟时间

class Solution {public int networkDelayTime(int[][] times, int n, int k) {List<int[]>[] graph = new LinkedList[n+1];for(int i = 1; i <= n; i ++){graph[i] = new LinkedList<int[]>();}for(int[] time : times){int from = time[0];int to = time[1];int w = time[2];graph[from].add(new int[]{to,w});}int[] result = dijkstra(k,graph);int res = 0;for(int i = 1; i < result.length; i ++){if(result[i] == Integer.MAX_VALUE){return -1;}res = Math.max(res,result[i]);}return res;}class State{int id;int distFromStart;public State(int id, int distFromStart){this.id = id;this.distFromStart = distFromStart;}}public int[] dijkstra(int start, List<int[]>[] graph){int n = graph.length;int[] result = new int[n];PriorityQueue<State> pq = new PriorityQueue<>((a,b)->{return a.distFromStart - b.distFromStart;});Arrays.fill(result,Integer.MAX_VALUE);result[start] = 0;pq.offer(new State(start,0));while(!pq.isEmpty()){State curV = pq.poll();int curId = curV.id;int curDistFromStart = curV.distFromStart;if(curDistFromStart > result[curId]){continue;}for(int[] next : graph[curId]){int nextId = next[0];int nextDist =  result[curId] + next[1];if(result[nextId] > nextDist){result[nextId] = nextDist;pq.offer(new State(nextId, result[nextId]));}}}return result;}
}