🍅5.Dijkstra核心代码实现
为了方便大家理解和记忆，我将代码按照上面的逻辑分成几个板块方便大家记忆。
1.初始化操作
//所有距离初始化为正无穷 Arrays.fill(dist,0x3f3f3f3f); //起点初始化为0，主要看起点的编号是几，这里默认为1 dist[1]=0;
2.寻找找到距离起点最近且未标记过的点
int t=-1; for(int j=1;j<=n;++j) { if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; } st[t]=true;
t表示距离起点最近且未标记过的点，刚开始默认为-1，表示没有，然后依次遍历所有的点，首先必须要保证该点未使用过，所以st[j]必须为flase。其次如果t=-1说明t还没选定，那么说明可以直接选择该点，然后如果当前dist[j]<dist[t]说明我们找到一个更小的点了，于是将t更新为这个更小的点。当然别忘记让st[t]为true。
3.利用步骤2找到的点去更新其他点的最短路径
for(int j=1;j<=n;++j){ dist[j]=Math.min(dist[j],dist[t]+g[t][j]); }
判断的方法和我们前面的样例说的是一模一样的，这样更新下每个点就好。
完整函数核心代码：
static int dijkstra(){ //填充函数 Arrays.fill(dist,0x3f3f3f3f); dist[1]=0; //因为总共有n个点，所以我们要迭代n次 for(int i=0;i<n;++i){ int t=-1; for(int j=1;j<=n;++j){ if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; } if(t==n) break; st[t]=true; for(int j=1;j<=n;++j){ dist[j]=Math.min(dist[j],dist[t]+g[t][j]); } } //当遍历完毕以后如果到点n的距离仍然是无穷大 //说明无法从起点到达该点，我们返回-1，反正dist[n]就是到n的最短距离 if(dist[n]==0x3f3f3f3f) return -1; else return dist[n]; }
🍆6.最短路模板题练手
🍦1.网络延迟时间
题目链接：网络延迟时间https://leetcode-cn.com/problems/network-delay-time/
为了方便大家练习，我就从力扣上找了模板题给大家练习。
首先大家遇到最短路径问题，一定要先分析数据规模，本题的n最大为100，所以我们是可以使用朴素的Dijkstra。我们直接套用上面的模板即可。
但是这题有几个需要注意的地方：
1.什么时候返回-1？
因为要达到所有的点，所以当我们判断到某个点的最短路径是正无穷时，说明无法到达，返回-1
2.最大时间是多少？
因为要保证所有节点都收到信息，所以所有结点收到信息的时间也就是最后一个结点收到的时间，我们在到达所有节点的世界里取一个max即可。
代码转换：
class Solution { int N=110; int[][] g=new int[N][N]; int[] dist=new int[N]; boolean[] st=new boolean[N]; public int networkDelayTime(int[][] times, int n, int k) { for(int i=0;i<=n;++i){ Arrays.fill(g[i],0x3f3f3f3f); } for(int[] nums:times){ int a=nums[0]; int b=nums[1]; int c=nums[2]; g[a][b]=c; } return dijkstra(n,k); } int dijkstra(int n,int k){ Arrays.fill(dist,0x3f3f3f3f); dist[k]=0; for(int i=0;i<n;++i){ int t=-1; for(int j=1;j<=n;++j){ if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j; } st[t]=true; for(int j=1;j<=n;++j){ dist[j]=Math.min(dist[j],dist[t]+g[t][j]); } } int res=0; for(int j=1;j<=n;++j){ if(dist[j]==0x3f3f3f3f) return -1; res=Math.max(res,dist[j]); } return res; } }
🍸2.到达目的的总方案数
你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。
给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 10^9 + 7 取余 后返回。
题目链接：到达目的地的方案数https://leetcode-cn.com/problems/number-of-ways-to-arrive-at-destination/
这道题是力扣某一周的周赛题，同样数据范围比较小，所以我们可以使用朴素的Dijkstra，但要注意这道题值的范围很大，所以无穷大值我们不能使用0x3f3f3f3f了。因为是统计到达的方案数，所以我们还需要使用一个cnt数组来统计到达每个位置的方案数，相当于是有点最短路+动态规划的感觉了。
代码转换：
class Solution { int N=210; long[][] g=new long[N][N]; boolean[] st=new boolean[N]; long[] dist=new long[N]; long INF = (Long.MAX_VALUE >> 1) - (long)1e5; int MOD = (int)1e9 + 7; int max=1; int[] cnt=new int[N]; public int countPaths(int n, int[][] roads) { for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ g[i][j]=INF; } } for(int[] s:roads){ int a=s[0]; int b=s[1]; int w=s[2]; g[a][b]=g[b][a]=w; } return Dijkstra(n); } int Dijkstra(int n){ Arrays.fill(dist,INF); dist[0]=0; cnt[0]=1; for(int i=0;i<n;++i){ int t=-1; for(int j=0;j<n;++j){ if(!st[j]&&(t==-1||dist[t]>dist[j])){ t=j; } } st[t]=true; for(int j=0;j<n;++j){ if(dist[t]+g[t][j]<dist[j]){ dist[j]=dist[t]+g[t][j]; cnt[j]=cnt[t]; }else if(dist[t]+g[t][j]==dist[j]){ cnt[j]=(cnt[j]+cnt[t])%MOD; } } } return cnt[n-1]; } }
🍓7.堆优化版Dijkstra
朴素版的Dijkstra的时间复杂度为O(n^2)，所以在点的数量变多时非常容易TLE，因此我们想到对原有的Dijkstra进行优化。
那我们应该对哪一部分进行优化呢？
我们有一个每次查找取出距离起点最小值的操作，所以我们可以想到利用优先队列进行优化，每次可以在O(1)的时间复杂度内取出距离起始点最近的点。
思路过程：
前面的过程一样，首先我们需要将起点放入优先队列中，然后进行一个while(!queue.isEmpty)的操作，类似BFS算法。每次取出距离最小的点，当然如果该点已经被取出来过那我们就应该continue，原理同朴素Dijkstra一样。然后我们同样使用该点进行相同的操作，去更新其他点的最短距离，每次更新一个点后，我们应该同时将其放入队列，让它继续去更新其他的边，因此最终完成的效率是O(mlogn)，m是边数。
完整代码转换：
import java.util.*; public class Main { static int N=100010; static int n,m; static int[] dist=new int[N]; static boolean[] st=new boolean[N]; //领接表 static Map<Integer,List<Node>> adj=new HashMap<>(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); while (m-->0){ int a=sc.nextInt(); int b=sc.nextInt(); int w=sc.nextInt(); if (!adj.containsKey(a)) adj.put(a,new ArrayList<>()); adj.get(a).add(new Node(b,w)); } int t=dijkstra(); System.out.println(t); } //核心代码 static int dijkstra(){ Arrays.fill(dist,0x3f3f3f3f); dist[1]=0; PriorityQueue<int[]> heap=new PriorityQueue<>((a,b)->a[1]-b[1]);//小顶堆 heap.offer(new int[]{1,0}); while (!heap.isEmpty()){ //每次放出距离最小的点 int[] t=heap.poll(); int ver=t[0],distance=t[1]; //已经遍历过该点，直接跳过 if (st[ver]) continue; st[ver]=true; //更新和最小节点相连的点 List<Node> list=adj.get(ver); if (list==null) continue; for (Node node:list){ int idx=node.idx; if (dist[idx]>distance+node.d){ dist[idx]=distance+node.d; heap.offer(new int[]{idx,dist[idx]}); } } } return dist[n]==0x3f3f3f3f?-1:dist[n]; } } class Node{ int idx; int d; public Node(int idx, int d) { this.idx = idx; this.d = d; } }
优化版的Dijkstra习题就没准备了，前面的两题都可以改成堆优化版的Dijkstra，大家也可以自行找习题训练。
