🍋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的最短距离。