⭐️引言⭐️ 

              大家好啊，我是执梗。图论算法可以说在算法中，是占比非常大且重要的一块内容，除去基础的DFS和BFS算法，最重要的就是我们的最短路径算法。最短路径算法是一块比较复杂的内容，因为它所使用的算法内容较多——有朴素版Dijkstra、堆优化版Dijkstra、bellman-ford、spfa、Floyd等。对于不同的情况，我们需要选择适合的算法，不然就很可能产生TLE。今天我带大家学习一下最基础的Dijkstra。

 📒博客首页：执梗的博客

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

❤️ ：热爱Java与算法学习，期待一起交流！

🙏作者水平很有限，如果发现错误，求告知，多谢！

🌺有问题可私信交流！！！

👻高校算法学习社区：高校算法学习社区

一起加入刷题内卷大军，还可以加入专属内卷群

⭐️目录⭐️

🍋1.什么是最短路径问题？

🍈2.什么是Dijkstra算法？

🍐3.Dijkstra算法的成员变量

🍍4. Dijkstra的样例流程

🍅5.Dijkstra核心代码实现

🍆6.最短路模板题练手

      🍦1.网络延迟时间

     🍸2.到达目的的总方案数

🍓7.堆优化版Dijkstra

☀️8.课后总结（社区纳新）

---

🍋1.什么是最短路径问题？

       既然知道Dijkstra是用来解决最短路径问题，那我们肯定要先清楚是最短路径问题。最短路径通俗的来说，就是在一个图中，从一个起始源点，到另外一个点的最小代价。为什么是最小代码而不是最短路径？

       因为可能题意说的并不是距离，也有可能是需要花费的金钱或者时间等，但其实都是最短路径问题的模型。

 🍈2.什么是Dijkstra算法？

        Dijkstra有两种，一种是朴素的Dijkstra算法，时间复杂度为O（n^2)，n是图中的点数。另外一种是堆优化版本的Dijkstra，时间复杂度是O(mlongn)，n是图中的点数，而m是图中边的数量。对于为什么能优化，我们在后面会详细介绍，但其实两者的核心原理是一样的。

        首先，Dijkstra是一种基于贪心思想的算法。用来解决带有非负权值的有向图或者无向图的单源最短路问题。一定要注意Dijkstra只适用于正权值的单源最短路问题，对于带有负权值的问题我们不可使用Dijkstra算法，需要使用其他算法。

       算法思路：

       Dijkstra首先会找到一个距离起点最近的点且该点并未确定好最短距离，然后再利用该点去更新其他点的最短距离。就比如有ABCDE五个地点，A为起点，首先找到了距离A点最近的点是B点，这时我们去判断一下从A点直接走到C、D、E点和先从A走到B再从B走到C、D、E点哪一种路劲更短，我们更新一个更小的值。

       上面的思想大概就是Dijkstra的核心，但具体需要如何完成我们还是需要用例子来讲解

 🍐3.Dijkstra算法的成员变量

        为了方便后续大家更好的理解Dijkstra算法和不会对代码产生疑问，我们首先要来了解和学习一下Dijkstra算法需要哪些成员变量。

        1.int类型的dist[]数组

//保存源点到各个顶点的最短距离
    static int[] dist=new int[N];

         dist的意思原为distance，翻译过来也就是距离的意思，因为是求最短路径，所以肯定需要有数组来记录记录。dist数组记录的是点到起点的最短距离，一般在初始化的时候，我们需要将整个数组初始化为无穷大，因为无穷大代表无法达到，每次更新时因为会取最小值，所以如果一个点起点无法到达它，那它最后的值肯定还是无穷大。

        然后要将dist[start]赋值为0，start是我们的起点，具体是哪个点看题意而定，一般都是编号为1的点。为什么要赋值为0呢？起点到起点自己的距离当然为0啦。

       2.boolean类型的st[]数组

//用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新
    static boolean[] st=new boolean[N];

        st数组的含义类似我们在BFS和DFS钟的作用，都是为了记录已经遍历过的点，我们每次找到距离起点最近的点时，这个点应该是我们之前没有选择过的。因为找到距离起点最近的点是为了用它去更新其他的点，如果此时它已经被使用过了那么再找他就毫无意义，所以每次使用完以后我们要将该点标记为true。   

        3.邻接矩阵g[][]

//g[i][j]表示i号点到达j号点的距离
static int[][] g=new int[N][N];

        既然是图论题目肯定需要有东西来存储图，而我们常用的便是邻接矩阵（稠密图常用）和邻接表（稀疏图常用）。

        这里我们为了方便理解使用的是邻接矩阵，g[i][j]表示的是从i点走到j点的距离

---

🍍4. Dijkstra的样例流程

        首先我们有这样的一张有向图，其中点v1是起点。

                       

          刚刚说了我们的Dijkstra需要数组dist和st。于是我们初始化有了这样两个数组，st默认全为false。而dist根据刚才的含义，我们的两个数组初始值应该是

        1.找到距离起点最近且未标记过的点

         根据前面我们说的做法，我们首先要找到一个距离起点最近的点且未被标记过的点，根据上图我们可以知道。这个符合的点肯定首先会找到起点自己，因为dist[1]是0嘛，肯定是最小的，然后再去用它更新其他点的距离，经过更新以后dist和st数组的值就应该变成了

      为什么有的点还是正无穷？

       因为我们此时找到的是起点，所以我们只能从用从起点去更新其他点，而起点1号点相连的只有3,5,6号点，而我们dist数组的3，5，6下标的值都还是正无穷，所以我们取更小的值。当然完事以后别忘记把st[1]标记为true，表示已经搜索过这个点。

---

       接下来我们继续重复的步骤。

       仍然是找到距离起点最近且未标记过的点。这次我们找到的是3号点。还是应用相同相同的判断逻辑，首先我们从图中可以看出，从3号点能直接到达的点只有4号点，这时候我们就要用贪心的思想去判断了——究竟是从1号点直接走到4号点近，还是从1号点走到3号点再走到4号点近？

        我们直接比较dist的值即可。通过判断可知dist[4]>dist[3]+g[3][4]（不知道g[3][4]什么含义上去看看成员变量的介绍）。所以我们要更新dist[4]的值为dist[3]+g[3][4]。然后再将st[3]变为true。数组的值会变成：

---

      接下来我们继续重复的步骤。

      这次我们找到的点应该是5号点，因为st为false且dist最小的就是5号点了。

      然后可知5号点能直达的点有4号点和6号点，然后我们开始判断：

      dist[4]=60>dist[5]+g[5][4]=30+20=50，所以我们将dist[4]更新为50

     dist[6]=100>dist[5]+g[5][6]=30+60=90，所以我们将dist[6]更新为90

     所以两个数组的值将更新为：            

           看到这里我相信你应该能明白这个算法的核心思想了，我也就不过多往下找了，重要的是向大家完成代码的实现。

           如果继续查找就会找到此时的点为4号点，而4号点能到达六号点，加以判断出:

           dist[6]=90>dist[4]+g[4][6]=50+10=60，所以dist[6]会变为60。最终代码的结束也就是st全变为true。此时dist[j]也就表示起点到点j的最短距离。

🍅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.网络延迟时间

             

题目链接：网络延迟时间

       为了方便大家练习，我就从力扣上找了模板题给大家练习。

       首先大家遇到最短路径问题，一定要先分析数据规模，本题的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 取余 后返回。

题目链接：到达目的地的方案数        

        这道题是力扣某一周的周赛题，同样数据范围比较小，所以我们可以使用朴素的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，大家也可以自行找习题训练。

---

☀️8.课后总结（社区纳新）

        最短路算法的算法很多，不同的场景下需要应用到不同的算法，经常容易产生学习了一个新算法而忘记了前面所学习的，所以大家一定要温故而知新，多刷题和默写模板，这样才能在有压力的环境下AC。Dijkstra的算法是最基础的最短路算法，大家更是应该烂熟于心。

        一个人坚持不了刷题？来高校算法学习社区吧！

      高校算法学习社区

1. 为了集合学习算法爱好者，共同打造一流算法学习氛围，各类大佬开展算法打卡活动，奖励丰富
2. 总榜奖励：（截止于2023年4月1日）

1.总榜第一：现金三百元

2.总榜第二与第三：Acwing算法课一套（价值150元可提现）

月榜：（从2020.年4月1日开始，每月一号结算）

1.月榜前三：请喝奶茶一杯

       社区已被官方推荐在主页，同步文章有流量加持，坚持算法打卡同步文章还能每月搞杯奶茶喝。社区发展阶段，早日加入成为元老，一起成为高校算法内卷分子吧！

       目前社区内有acmer手把手带刷的的每日一题普及组以及提高组，学习算法没有方向就快来加入我们吧。

       社区地址：https://bbs.csdn.net/forums/Suanfa（社区右下角可加入专属内卷群）

       社区更多详细和玩法：高校算法社区玩法

           如果文章对你有所帮助，还望能给点三连支持一下，非常感谢！！！